On-line Planar Graph Embedding

1996/09/01 by Roberto Tamassia · 13 citations
Computer Science · Engineering · Mathematics · #Artificial intelligence #Book embedding #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Data structure #Discrete mathematics #Embedding #Graph #Graph embedding #Interconnection Networks and Systems #Line graph #Mathematics #Pathwidth #Planar #Planar graph #Planar straight-line graph #Preprocessor #VLSI and FPGA Design Techniques

paper · doi:10.1006/jagm.1996.0044

published in Journal of Algorithms 21(2), 201-239 (Elsevier BV)

crossref issued 1996/09/01 · crossref published 1996/09/01 · crossref published-print 1996/09/01 · openalex publication_date 1996/09/01 · crossref created 2002/09/17 · crossref deposited 2019/05/09 · openalex created_date 2025/10/10 · crossref indexed 2025/10/11 · openalex updated_date 2026/07/28

Citations

• On-line graph algorithms with SPQR-trees
• A linear algorithm for embedding planar graphs using PQ-trees
• Automatic graph drawing and readability of diagrams
• Efficient Planarity Testing
• Incremental planarity testing
• Algorithms for plane representations of acyclic digraphs
• Maintaining bridge-connected and biconnected components on-line
• Convex Representations of Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On-Line Planarity Testing
• How to Draw a Graph
• Computing an st-numbering

Cited by

• On-line maintenance of triconnected components with SPQR-trees
• Fully-dynamic planarity testing in polylogarithmic time
• Planarity testing [wikipedia]