Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-12 Summary

Establishing Order in Planar Subdivisions, May 1987 David G. Kirkpatrick

A planar subdivision is the partition of the plane induced by an embedded planar graph. A representation of such a subdivision is {\em 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.

If you have any questions or comments regarding this page please send mail to