Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Efficient Planarity Testing
Authors: Hopcroft, John E.
Tarjan, Robert Endre
Keywords: computer science
technical report
Issue Date: Apr-1973
Publisher: Cornell University
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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
73-165.pdf2.35 MBAdobe PDFView/Open
73-165.ps1.24 MBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us