A linear algorithm for embedding planar graphs using PQ-trees
From MaRDI portal
This paper presents a simple linear algorithm for embedding (or drawing) a planar graph in the plane. The algorithm is based on the vertex- addition algorithm of \textit{A. Lempel}, \textit{S. Even}, and \textit{I. Cederbaum} [Theory of graphs, Int. Symp. Rome 1966, 215-232 (1967; Zbl 0197.502)] for the planarity testing, and is a modification of \textit{K. S. Booth} and \textit{G. S. Lueker}'s [J. Comput. Syst. Sci. 13, 335-379 (1976; Zbl 0367.68034)] implementation of the testing algorithm using a PQ-tree. Compared with the known embedding algorithm of \textit{J. E. Hopcroft} and \textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 21, 549-568 (1974; Zbl 0307.68025)], this algorithm is conceptually simple and easy to understand or implement. Moreover this embedding algorithm can find all the embeddings of a planar graph.
Recommendations
Cites work
- Computing an st-numbering
- Dividing a Graph into Triconnected Components
- Efficient Planarity Testing
- 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?)
- Parallel concepts in graph theory
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Cited in
(62)- Bijective counting of plane bipolar orientations and Schnyder woods
- Graph graphics: Theory and practice
- An efficient parallel algorithm for planarity
- Establishing order in planar subdivisions
- Algorithms for plane representations of acyclic digraphs
- Area requirement and symmetry display of planar upward drawings
- Planar graphs: Theory and algorithms
- On counting planar embeddings
- A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
- Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete
- A better heuristic for orthogonal graph drawings
- Projective plan and Möbius band obstructions
- Fixed edge-length graph drawing is NP-hard
- Disk embeddings of planar graphs
- Drawing planar graphs using the canonical ordering
- On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
- A new planarity test
- Metric dimension of maximal outerplanar graphs
- On the complexity of recognizing Wheeler graphs
- Planar rectilinear drawings of outerplanar graphs in linear time
- Treetopes and their graphs
- Discrete trace theorems and energy minimizing spring embeddings of planar graphs
- Tree-decompositions with bags of small diameter
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- Planar median graphs and cubesquare-graphs
- Elimination of local bridges
- Algorithms for Drawing Planar p-petal Graphs
- Planarity testing revisited
- Counting Embeddings of Planar Graphs Using DFS Trees
- scientific article; zbMATH DE number 434911 (Why is no real title available?)
- scientific article; zbMATH DE number 3873357 (Why is no real title available?)
- scientific article; zbMATH DE number 3929029 (Why is no real title available?)
- Ranking and unranking planar embeddings
- scientific article; zbMATH DE number 3968606 (Why is no real title available?)
- scientific article; zbMATH DE number 3968607 (Why is no real title available?)
- Planar embedding: linear-time algorithms for vertex placement and edge orderings
- Linkless and flat embeddings in 3-space
- scientific article; zbMATH DE number 4128415 (Why is no real title available?)
- scientific article; zbMATH DE number 1305401 (Why is no real title available?)
- Obstructions for the Disk and the Cylinder Embedding Extension Problems
- scientific article; zbMATH DE number 1522747 (Why is no real title available?)
- Faster computation of the Robinson-Foulds distance between phylogenetic networks
- Branch-and-bound techniques for the maximum planar subgraph problem∗
- scientific article; zbMATH DE number 841661 (Why is no real title available?)
- On triangulating planar graphs under the four-connectivity constraint
- A dichotomy result for cyclic-order traversing games
- Geometry and generation of a new graph planarity game
- Planarity algorithms via PQ-trees (extended abstract)
- Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges
- Practical Level Planarity Testing and Layout with Embedding Constraints
- scientific article; zbMATH DE number 2192203 (Why is no real title available?)
- Topological recognition of polyhedral objects from multiple views
- Find subtrees of specified weight and cycles of specified length in linear time
- Planarity for clustered graphs
- An annotated review on graph drawing and its applications
- Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges
- An improved integrality gap for disjoint cycles in planar graphs
- Efficient polynomial-time approximation scheme for the genus of dense graphs
- The Euclidean k-matching problem is NP-hard
- Drawing plane graphs nicely
- Dynamic maintenance of planar digraphs, with applications
- Upward drawings of triconnected digraphs.
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)
