On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm

1996/08/01 by Kurt Mehlhorn, K. Mehlhorn, Petra Mutzel +1 · 33 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Algorithm #Artificial intelligence #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Embedding #Mathematics #Planarity testing #Theory of computation

paper · open access · doi:10.1007/bf01940648

published in Algorithmica 16(2), 233-242 (Springer Science and Business Media LLC)

crossref issued 1996/08/01 · crossref published 1996/08/01 · crossref published-print 1996/08/01 · openalex publication_date 1996/08/01 · crossref created 2005/08/03 · crossref deposited 2019/05/13 · crossref indexed 2025/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

• A linear algorithm for embedding planar graphs using PQ-trees
• Efficient Planarity Testing
• How to draw a planar graph on a grid
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Computing an st-numbering

Cited by

• A new planarity test
• Planarity testing [wikipedia]