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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE