Efficient Planarity Testing

John Hopcroft, Robert Tarjan

Research output: Contribution to journalArticlepeer-review

807 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)549-568
Number of pages20
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Oct 1 1974
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Efficient Planarity Testing'. Together they form a unique fingerprint.

Cite this