Efficient Planarity Testing
John E. Hopcroft, Robert Endre Tarjan · Journal of the ACM · 1974
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 1,081 works. doi:10.1145/321850.321852 Open-access PDF
Authors
References
- Graph theory
- GRAPH THEORY
- Complexity of Computer Computations
- Depth-First Search and Linear Graph Algorithms
- Theory of graphs
- The Theory of Graphs and Its Applications
- Review of "Problem-Solving Methods in Artificial Intelligence by Nils J. Nilsson", McGraw-Hill Pub.
- Backtrack Programming
- Finite Graphs and Networks, An Introduction with Applications.
- Sur le problème des courbes gauches en Topologie