CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
authors Gross, Jonathan L. and Rosen, Ronald H.
year 1979
title A Linear Time Planarity Algorithm for 2-Complexes
source Journal of the Association for Computing Machinery. October, 1979. vol. 26: pp. 611-617 : 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 depth-first search both in application of the graph planarity algorithm of Hopcroft and Tarjan and elsewhere
keywords algorithms, complexity, depth-first, search, topology, graphs, computational geometry,
series CADline
references Content-type: text/plain
last changed 2003/06/02 11:58
pick and add to favorite papersHOMELOGIN (you are user _anon_950934 from group guest) CUMINCAD Papers Powered by SciX Open Publishing Services 1.002