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

DOI10.1007/BF01940648zbMath0854.68075WikidataQ56977504 ScholiaQ56977504MaRDI QIDQ1920431

Kurt Mehlhorn, Petra Mutzel

Publication date: 20 October 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

planarity testing algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, An annotated review on graph drawing and its applications, Using Brouwer’s Fixed Point Theorem, Graphs with no \(K_{3,3}\) minor containing a fixed edge, A new planarity test, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, Tree \(t\)-spanners in outerplanar graphs via supply demand partition

Uses Software

• LEDA

Cites Work

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