Accession Number:

AD0738027

Title:

An Efficient Planarity Algorithm,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Tarjan,Robert E.

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:

• (*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