authors 
Gross, Jonathan L. and Rosen, Ronald H. 
year 
1979 
title 
A Linear Time Planarity Algorithm for 2Complexes 
source 
Journal of the Association for Computing Machinery. October, 1979. vol. 26: pp. 611617 : ill. includes bibliography 
summary 
A linear time algorithm to decide whether a given finite 2 complex is planar is described. Topological results of Gross, Harary and Rosen are the mathematical basis for the algorithm. Optimal running time is achieved by constructing various lists simultaneously and keeping their orderings compatible. If the complex is simplical with p vertices, then the algorithm has O(p) time and space bounds. The algorithm uses depthfirst search both in application of the graph planarity algorithm of Hopcroft and Tarjan and elsewhere 
keywords 
algorithms, complexity, depthfirst, search, topology, graphs, computational geometry, 
series 
CADline 
references 
Contenttype: text/plain

last changed 
2003/06/02 11:58 
