Hopcroft, John E.Tarjan, Robert Endre2007-04-192007-04-191973-04http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-165https://hdl.handle.net/1813/6011This 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.2409135 bytes1273475 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report