The two basic linear time Planarity algorithms: Are they the same?

DOI10.1080/03081089008817982zbMath0718.05023OpenAlexW2049023613MaRDI QIDQ5749306

E. Rodney Canfield, S. Gill Williamson

Publication date: 1990

Published in: Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/03081089008817982

zbMATH Keywords

Hopcroft-Tarjan algorithmLempel-Even- Cederbaum algorithmplanarity testing algorithms

Mathematics Subject Classification ID

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

Related Items (4)

Bijective comparison of optimal planarity algorithms ⋮ Gap strings and spanning forests for bridge graphs of biconnected graphs ⋮ A matrix analysis of carrier posets of biconnected graphs ⋮ Canonical forms for cycles in bridge graphs

Cites Work

• Computing an st-numbering
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Ranking and unranking planar embeddings
• Efficient Planarity Testing
• Unnamed Item

This page was built for publication: The two basic linear time Planarity algorithms: Are they the same?