# The ICICS/CS Reading Room

## UBC CS TR-87-12 Summary

- No on-line copy of this technical report is available.

- 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
help@cs.ubc.ca.