JavaScript is disabled for your browser. Some features of this site may not work without it.
Efficient Planarity Testing

Author
Hopcroft, John E.; Tarjan, Robert Endre
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 uses 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 successfully tested graphs with as many as 900 vertices in less than 12 seconds.
Date Issued
1973-04Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-165
Type
technical report