
Accession Number : AD0738027
Title : An Efficient Planarity Algorithm,
Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s) : Tarjan,Robert E.
Report Date : NOV 1971
Pagination or Media Count : 158
Abstract : An efficient algorithm is presented for determining whether a graph G can be embedded in the plane. Depthfirst search, or backtracking, is the most important of the techniques used by the algorithm. If G has V vertices, the algorithm requires O(V) space and O(V) time when implemented on a tandom access computer. An implementation on the Stanford IBM 360/67 successfully analyzed graphs with as many as 900 vertices in less than 12 seconds. (Author)
Descriptors : (*TOPOLOGY, GRAPHICS), GEOMETRY, MATRICES(MATHEMATICS), SET THEORY, MAPPING(TRANSFORMATIONS), COMPUTER PROGRAMS, COMBINATORIAL ANALYSIS, ARTIFICIAL INTELLIGENCE, ALGORITHMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE