A new planarity test

DOI10.1016/S0304-3975(98)00120-0zbMath0930.05092WikidataQ56341894 ScholiaQ56341894MaRDI QIDQ1960413

Yanyan Li

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

depth-first search treeplanar embeddingsplanarity testlinear time testing algorithm

Mathematics Subject Classification ID

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 (20)

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 ⋮ Parameterizing path partitions ⋮ Simpler algorithms for testing two-page book embedding of partitioned graphs ⋮ Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings ⋮ Experimental comparison of PC-trees and PQ-trees ⋮ 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

• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: A new planarity test