Efficient Planarity Testing
- 1 October 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 21 (4) , 549-568
- https://doi.org/10.1145/321850.321852
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.Keywords
This publication has 10 references indexed in Scilit:
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973
- Testing flow graph reducibilityPublished by Association for Computing Machinery (ACM) ,1973
- A V2 algorithm for determining isomorphism of planar graphsInformation Processing Letters, 1971
- AN n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATONPublished by Elsevier ,1971
- A new planarity test based on 3-connectivityIEEE Transactions on Circuit Theory, 1970
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- Connectivity in GraphsPublished by University of Toronto Press Inc. (UTPress) ,1966
- A Simple and Efficient Algorithm for Determining Isomorphism of Planar Triply Connected GraphsIEEE Transactions on Circuit Theory, 1966
- Backtrack ProgrammingJournal of the ACM, 1965
- Sur le problème des courbes gauches en TopologieFundamenta Mathematicae, 1930