A linear algorithm for embedding planar graphs using PQ-trees

1985/02/01 by Norishige Chiba, Takao Nishizeki, Shigenobu Abe +1 · 200 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Artificial intelligence #Book embedding #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Embedding #Graph #Graph embedding #Interconnection Networks and Systems #Line graph #Mathematics #Pathwidth #Planar #Planar graph #Planarity testing #Simple (philosophy) #Vertex (graph theory)

paper · doi:10.1016/0022-0000(85)90004-2

published in Journal of Computer and System Sciences 30(1), 54-76 (Elsevier BV)

openalex publication_date 1985/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03

Citations

• Efficient Planarity Testing

Cited by

• Improved Erdős-Pósa inequalities for odd cycles in planar graphs
• Efficient polynomial-time approximation scheme for the genus of dense graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Testing Simultaneous Planarity when the Common Graph is 2-Connected
• Bijective counting of plane bipolar orientations and Schnyder woods
• On the Complexity of a Derivative Chess Problem
• Algorithms for drawing graphs: an annotated bibliography
• The disjoint separators problem in graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Algorithms for plane representations of acyclic digraphs
• Level Planar Embedding in Linear Time
• Linkless and flat embeddings in 3-space and the unknot problem
• Treetopes and Their Graphs
• Fixed edge-length graph drawing is NP-hard
• On-Line Planarity Testing
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• On-line Planar Graph Embedding
• A new planarity test
• Planarity testing [wikipedia]