A linear algorithm for embedding planar graphs using PQ-trees
From MaRDI portal
Publication:1083864
DOI10.1016/0022-0000(85)90004-2zbMath0605.68060OpenAlexW1964700557WikidataQ60304238 ScholiaQ60304238MaRDI QIDQ1083864
Shigenobu Abe, Norishige Chiba, Takao Nishizeki, 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
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Minimum strictly fundamental cycle bases of planar graphs are hard to find ⋮ Planar rectilinear drawings of outerplanar graphs in linear time ⋮ Tree-decompositions with bags of small diameter ⋮ Unnamed Item ⋮ Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete ⋮ Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges ⋮ Graph graphics: Theory and practice ⋮ Drawing planar graphs using the canonical ordering ⋮ On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm ⋮ Algorithms for plane representations of acyclic digraphs ⋮ A better heuristic for orthogonal graph drawings ⋮ Projective plan and Möbius band obstructions ⋮ Branch-and-bound techniques for the maximum planar subgraph problem∗ ⋮ Obstructions for the Disk and the Cylinder Embedding Extension Problems ⋮ 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 ⋮ Linkless and flat embeddings in 3-space ⋮ Treetopes and their graphs ⋮ Planar median graphs and cubesquare-graphs ⋮ Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ Faster computation of the Robinson-Foulds distance between phylogenetic networks ⋮ A new planarity test ⋮ Discrete trace theorems and energy minimizing spring embeddings of planar graphs ⋮ Area requirement and symmetry display of planar upward drawings ⋮ Upward drawings of triconnected digraphs. ⋮ Topological recognition of polyhedral objects from multiple views ⋮ On triangulating planar graphs under the four-connectivity constraint ⋮ Practical Level Planarity Testing and Layout with Embedding Constraints ⋮ Metric dimension of maximal outerplanar graphs ⋮ Fixed edge-length graph drawing is NP-hard ⋮ A dichotomy result for cyclic-order traversing games ⋮ Algorithms for Drawing Planar p-petal Graphs ⋮ Geometry and Generation of a New Graph Planarity Game ⋮ Bijective counting of plane bipolar orientations and Schnyder woods ⋮ Drawing plane graphs nicely ⋮ On counting planar embeddings ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs ⋮ On the complexity of recognizing Wheeler graphs
Cites Work
