Establishing order in planar subdivisions (Q1115185)

A planar subdivision is the partition of the plane induced by an embedded planar graph. A representation of such a subdivision is called ordered if for each vertex of the graph the clockwise sequence of edges in the graph appears explicitly. In this paper the input to the algorithm is an endpoint embedding of a graph \(G=(V,E)\) which is an assignment of locations in the plane to each vertex of V and an assignment of angles to each end of each edge of E describing its angle of incidence with the corresponding endpoint. An output in the form of an ordered representation is desired. The worst case complexity of converting an unordered representation into an ordered one is shown to be \(O(n+\log \lambda (G))\) where \(n=number\) of vertices of the graph G and \(\lambda\) (G) is the number of topologically distinct embeddings of G in the plane. The naive algorithm which explicitly sorts by angle all the edges at each vertex of G has complexity O(\(\sum_{v}k \log k)\) where \(k=\) degree of a typical vertex v. This can be as bad as O(n log n), for example, for \(K_{1,n-1}.\) The author's algorithm is based on the observation that establishing order at low degree vertices is cheap, that the average degree of a planar graph is low and that the order at certain vertices constrains the order at the other vertices. The algorithm is incremental: vertices are selected, ordered, and then removed. The idea of face shrinking is used to embed, within the reduced subdivision, information concerning the order already established at the removed vertex and the constraints imposed as a result on the remaining vertices. The notion of normal digraphs is defined in such a manner which includes the class of undirected graphs and it is shown that these normal digraphs are capable of expressing the constraints associated with partial embeddings of a given graph. The required data structures and pseudo code for the algorithm are provided as well as correctness and complexity analysis. The algorithm assumes that the given endpoint embedding of the graph does, in fact, have a planar realization. Checking the planar realizability of a given endpoint embedding is a separate issue. It is shown that this problem is O(n) reducible to the problem of establishing order.