Accession Number:
AD0738027
Title:
An Efficient Planarity Algorithm,
Descriptive Note:
Corporate Author:
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s):
Report Date:
1971-11-01
Pagination or Media Count:
158.0
Abstract:
An efficient algorithm is presented for determining whether a graph G can be embedded in the plane. Depth-first search, or backtracking, is the most important of the techniques used by the algorithm. If G has V vertices, the algorithm requires OV space and OV time when implemented on a tandom access computer. An implementation on the Stanford IBM 36067 successfully analyzed graphs with as many as 900 vertices in less than 12 seconds. Author
Descriptors:
Subject Categories:
- Theoretical Mathematics