Efficient Planarity Testing

John Hopcroft; Robert Tarjan

doi:10.1145/321850.321852

Efficient Planarity Testing

John Hopcroft
, Robert Tarjan

Research output: Contribution to journal › Article › peer-review

846 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 language	English (US)
Pages (from-to)	549-568
Number of pages	20
Journal	Journal of the ACM (JACM)
Volume	21
Issue number	4
DOIs	https://doi.org/10.1145/321850.321852
State	Published - Oct 1 1974
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1145/321850.321852

Cite this

@article{6afa3d9f1a0e4344ae8587a96541ba85,

title = "Efficient Planarity Testing",

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.",

author = "John Hopcroft and Robert Tarjan",

year = "1974",

month = oct,

day = "1",

doi = "10.1145/321850.321852",

language = "English (US)",

volume = "21",

pages = "549--568",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Efficient Planarity Testing

AU - Hopcroft, John

AU - Tarjan, Robert

PY - 1974/10/1

Y1 - 1974/10/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0016117886

UR - https://www.scopus.com/pages/publications/0016117886#tab=citedBy

U2 - 10.1145/321850.321852

DO - 10.1145/321850.321852

M3 - Article

AN - SCOPUS:0016117886

SN - 0004-5411

VL - 21

SP - 549

EP - 568

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 4

ER -

Efficient Planarity Testing

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this