A linear algorithm for embedding planar graphs using PQ-trees

DOI10.1016/0022-0000(85)90004-2MaRDI QIDQ1083864zbMATH OpenOpenAlexWikidataFDO

Authors Norishige Chiba, Takao Nishizeki, Shigenobu Abe, Takao Ozawa

Publication date 1985

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(85)90004-2

zbMATH Keywords

planar graphlinear algorithmplanarity testingembedding algorithmvertex addition algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• scientific article; zbMATH DE number 1305401
• A linear-time algorithm for drawing a planar graph on an \((n-2)\times (n-2)\) grid.
• Planarity algorithms via PQ-trees (extended abstract)
• Planar embedding: linear-time algorithms for vertex placement and edge orderings
• A new planarity test

Cites work

• scientific article; zbMATH DE number 3885930 (Why is no real title available?)
• scientific article; zbMATH DE number 3165199 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• Computing an st-numbering
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• Parallel concepts in graph theory
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(58)

• scientific article; zbMATH DE number 4128415 (Why is no real title available?)
• scientific article; zbMATH DE number 3873357 (Why is no real title available?)
• Fixed edge-length graph drawing is NP-hard
• scientific article; zbMATH DE number 3968607 (Why is no real title available?)
• An annotated review on graph drawing and its applications
• Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges
• scientific article; zbMATH DE number 841661 (Why is no real title available?)
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• scientific article; zbMATH DE number 3968606 (Why is no real title available?)
• Projective plan and Möbius band obstructions
• scientific article; zbMATH DE number 1522747 (Why is no real title available?)
• Drawing plane graphs nicely
• A better heuristic for orthogonal graph drawings
• Metric dimension of maximal outerplanar graphs
• Linkless and flat embeddings in 3-space
• Topological recognition of polyhedral objects from multiple views
• scientific article; zbMATH DE number 3929029 (Why is no real title available?)
• Discrete trace theorems and energy minimizing spring embeddings of planar graphs
• scientific article; zbMATH DE number 434911 (Why is no real title available?)
• On counting planar embeddings
• An efficient parallel algorithm for planarity
• Geometry and generation of a new graph planarity game
• Find subtrees of specified weight and cycles of specified length in linear time
• Area requirement and symmetry display of planar upward drawings
• Graph graphics: Theory and practice
• Disk embeddings of planar graphs
• Tree-decompositions with bags of small diameter
• A dichotomy result for cyclic-order traversing games
• Planar rectilinear drawings of outerplanar graphs in linear time
• Algorithms for plane representations of acyclic digraphs
• Planarity for clustered graphs
• Elimination of local bridges
• Planar median graphs and cubesquare-graphs
• Ranking and unranking planar embeddings
• scientific article; zbMATH DE number 2192203 (Why is no real title available?)
• A new planarity test
• Drawing planar graphs using the canonical ordering
• Establishing order in planar subdivisions
• Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
• Planar graphs: Theory and algorithms
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Bijective counting of plane bipolar orientations and Schnyder woods
• Treetopes and their graphs
• Counting Embeddings of Planar Graphs Using DFS Trees
• Algorithms for Drawing Planar p-petal Graphs
• Upward drawings of triconnected digraphs.
• Planarity algorithms via PQ-trees (extended abstract)
• On triangulating planar graphs under the four-connectivity constraint
• Dynamic maintenance of planar digraphs, with applications
• Faster computation of the Robinson-Foulds distance between phylogenetic networks
• Minimum strictly fundamental cycle bases of planar graphs are hard to find
• Branch-and-bound techniques for the maximum planar subgraph problem^∗
• Practical Level Planarity Testing and Layout with Embedding Constraints
• On the complexity of recognizing Wheeler graphs
• Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges
• Planarity testing revisited
• Planar embedding: linear-time algorithms for vertex placement and edge orderings
• Obstructions for the Disk and the Cylinder Embedding Extension Problems

This page was built for publication: A linear algorithm for embedding planar graphs using PQ-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083864)