A linear algorithm for embedding planar graphs using PQ-trees

1985/02/01 by Norishige Chiba, Takao Nishizeki, Shigenobu Abe +1 · 6 citations
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Interconnection Networks and Systems

paper · doi:10.1016/0022-0000(85)90004-2

Citations

• Efficient Planarity Testing

Cited by

• Improved Erdős-Pósa inequalities for odd cycles in planar graphs
• Efficient polynomial-time approximation scheme for the genus of dense graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Testing Simultaneous Planarity when the Common Graph is 2-Connected
• Bijective counting of plane bipolar orientations and Schnyder woods
• On the Complexity of a Derivative Chess Problem