A Linear Time Planarity Algorithm for 2-Complexes
Jonathan L. Gross, Ronald H. Rosen · Journal of the ACM · 1979
A hnear 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 Opttmal running time is achieved by constructing various hsts simultaneously and keeping their ordermgs compatible If the complex is stmphcial with p vertices, then the algorithm has O(p) time and space bounds The algorithm uses depth-first search both m application of the graph plananty algorithm of Hopcroft and Tarjan and elsewhere