Establishing Order in Planar Subdivisions

David G. Kirkpatrick
Publishing date
May 1987

A planar subdivision is the partition of the plane induced by an embedded planar graph. A representation of such a subdivision is ordered if, for each vertex $\upsilon$ of the associated graph $G$, the (say) clockwise sequence of edges in the embedding of $G$ incident with appears explicitly. The worst-case complexity of establishing order in a planar subdivision --- i.e. converting an unordered representation into an ordered one --- is shown to be \( \Theta (n + \log \lambda(G)) \), where $n$ is the size (number of vertices) of the underlying graph $G$ and $\lambda (G)$ is the number of topologically distinct embeddings of $G$ in the plane.