Efficient Planarity Testing

John Hopcroft, Robert Tarjan

Research output: Contribution to journalArticle

717 Scopus citations

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 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)
Volume21
Issue number4
DOIs
StatePublished - Oct 1 1974
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

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

  • Cite this