Efficient Planarity Testing

1974/10/01 by John Hopcroft, John E. Hopcroft, Robert E. Tarjan +1 · 19 citations
Computer Science · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Graph Theory and Algorithms

paper · pdf · doi:10.1145/321850.321852

Abstract

This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter and correctly formulated by Goldstein. The algorithm used depth-first search and has O ( V ) time and space bounds, where V is the number of vertices in G . An ALGOL implementation of the algorithm succesfully tested graphs with as many as 900 vertices in less than 12 seconds.

Cited by

• A linear algorithm for embedding planar graphs using PQ-trees
• Approximation algorithms for NP-complete problems on planar graphs
• Street Network Models and Indicators for Every Urban Area in the World
• The Generalized Independent and Dominating Set Problems on Unit Disk Graphs
• Efficient polynomial-time approximation scheme for the genus of dense graphs
• String graphs are quasi-isometric to planar graphs
• Distributed Interactive Proofs for Planarity with Log-Star Communication
• Liar's vertex-edge domination in unit disk graph
• Proof of a conjecture of Voss on bridges of longest cycles
• Testing Depth First Search Numbering
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Placing and routing quantum LDPC codes in multilayer superconducting hardware
• A Log-space Algorithm for Canonization of Planar Graphs
• Multiple-source multiple-sink maximum flow in planar graphs
• Planar Multiway Cut with Terminals on Few Faces
• Total Domination in Unit Disk Graphs
• A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
• BPLLDA: Predicting lncRNA-Disease Associations Based on Simple Paths With Limited Lengths in a Heterogeneous Network. [europepmc]
• Addressing the Return Visit Challenge in Autonomous Flying Ad Hoc Networks Linked to a Central Station. [europepmc]

Related

• A Planarity Test via Construction Sequences
• A Simple Partially Embedded Planarity Test Based on Vertex-Addition
• Planarity Testing Revisited
• An Experimental Study of a 1-planarity Testing and Embedding Algorithm
• Fully-dynamic Planarity Testing in Polylogarithmic Time