| 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 13:58 |
|
