Efficient Planarity Testing

1974/10/01 by John Hopcroft, John E. Hopcroft, Robert E. Tarjan +1 · 1,082 citations
Computer Science · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Digital Image Processing Techniques #Graph #Graph Theory and Algorithms #Mathematics #Planarity testing #Plane (geometry) #Theoretical computer science

paper · pdf · doi:10.1145/321850.321852

published in Journal of the ACM 21(4), 549-568 (Association for Computing Machinery)

openalex publication_date 1974/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26

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
• Engineering DFS-Based Graph Algorithms
• Planar Reachability Under Single Vertex or Edge Failures
• A first view on the density of 5-planar graphs
• Planarity Testing Revisited
• A topological characterization of Gauss codes
• Crossing minimization in linear embeddings of graphs
• Embedding planar graphs in four pages
• Algorithms for drawing graphs: an annotated bibliography
• A characterization of terminal planar networks by forbidden structures
• New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
• Untangling a Planar Graph
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• TRÉMAUX TREES AND PLANARITY
• Computing crossing numbers in quadratic time
• Computing crossing number in linear time
• Finding Minimum Spanning Trees
• The clique problem for planar graphs
• Graph visualization and navigation in information visualization: A survey
• Upward planarity testing
• Optimal upward planarity testing of single-source digraphs
• Chapter 8 Algorithmic implications of the graph minor theorem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Depth-first search is inherently sequential
• The Rectilinear Steiner Tree Problem is NP-Complete
• How to draw a planar graph on a grid
• Small sets supporting fary embeddings of planar graphs
• Parallel Algorithms in Graph Theory: Planarity Testing
• Linkless and flat embeddings in 3-space and the unknot problem
• The computational complexity of knot and link problems
• The number of Reidemeister moves needed for unknotting
• A Linear Recognition Algorithm for Cographs
• On the Complexity of Metric Dimension
• Isomorphism testing for graphs of bounded genus
• Planar Graph Isomorphism is in Log-Space
• Graph isomorphism problem
• On Floor-Plan of Plane Graphs
• A generalization and proof of the Aanderaa-Rosenberg conjecture
• Planar minimally rigid graphs and pseudo-triangulations
• Treetopes and Their Graphs
• Gauss codes, planar hamiltonian graphs, and stack-sortable permutations
• Classes of cycle bases
• Fixed edge-length graph drawing is NP-hard
• Planar orientations with low out-degree and compaction of adjacency matrices
• A Computational Approach to Conway’s Thrackle Conjecture
• A Linear Time Implementation of SPQR-Trees
• On-Line Planarity Testing
• Incremental planarity testing
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Path-based depth-first search for strong and biconnected components
• Computing an st-numbering
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• On-line Planar Graph Embedding
• A new planarity test
• Alpha-algorithms for incremental planarity testing (preliminary version)
• Depth-First Search and Kuratowski Subgraphs
• Fully dynamic planarity testing with applications
• Fully-dynamic planarity testing in polylogarithmic time
• Recognizing String Graphs Is Decidable
• A Separator Theorem for Planar Graphs
• Guthrie's problem: new equivalences and rapid reductions
• Finding small simple cycle separators for 2-connected planar graphs
• A 3-approximation for the pathwidth of Halin graphs
• Convex drawings of graphs in two and three dimensions (preliminary version)
• Planar median graphs and cubesquare-graphs
• Planarity Allowing Few Error Vertices in Linear Time
• Planarity testing [wikipedia]
• 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