Planarity Algorithms via PQ-Trees (Extended Abstract)

DOI10.1016/j.endm.2008.06.029zbMath1267.05088OpenAlexW2059074458MaRDI QIDQ5300998

Bernhard Haeupler, Robert Endre Tarjan

Publication date: 28 June 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2008.06.029

zbMATH Keywords

planarity testingvertex addition method

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

An annotated review on graph drawing and its applications ⋮ Consecutive Ones Property Testing: Cut or Swap ⋮ On the complexity of recognizing Wheeler graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Computing an st-numbering
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• PC trees and circular-ones arrangements.
• A new planarity test
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Efficient Planarity Testing
• TRÉMAUX TREES AND PLANARITY

This page was built for publication: Planarity Algorithms via PQ-Trees (Extended Abstract)