A new planarity test
From MaRDI portal
Publication:1960413
DOI10.1016/S0304-3975(98)00120-0zbMath0930.05092WikidataQ56341894 ScholiaQ56341894MaRDI QIDQ1960413
Publication date: 12 January 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Planarity Algorithms via PQ-Trees (Extended Abstract), Linear-time recognition of map graphs with outerplanar witness, A simulated annealing algorithm for the maximum planar subgraph problem, Synchronized Planarity with Applications to Constrained Planarity Problems, Tree-representation of set families and applications to combinatorial decompositions, PC trees and circular-ones arrangements., An annotated review on graph drawing and its applications, A Note on the Practicality of Maximal Planar Subgraph Algorithms, Treetopes and their graphs, Errors in graph embedding algorithms, Affine and projective tree metric theorems, Simpler algorithms for testing two-page book embedding of partitioned graphs, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem, A dichotomy result for cyclic-order traversing games, Algorithms for Drawing Planar p-petal Graphs, Quantitative Restrictions on Crossing Patterns, Heuristics for the maximum outerplanar subgraph problem
Cites Work
- Unnamed Item
- Unnamed Item
- A linear algorithm for embedding planar graphs using PQ-trees
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
- Depth-First Search and Kuratowski Subgraphs
- Efficient Planarity Testing
- An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
