×

Establishing order in planar subdivisions. (English) Zbl 0663.68053

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.
Reviewer: R.Shantaram

MSC:

68Q25 Analysis of algorithms and problem complexity
05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974. · Zbl 0326.68005
[2] B. G. Baumgart, A polyhedron representation for computer vision,AFIPS Conference Proceedings, Vol. 44 (1975 National Computer Conference, Anaheim, CA), AFIPS Press, Montvale, NJ, 1975, pp. 589-596.
[3] M. Ben-Or, Lower bounds for algebraic computation trees,Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 80-86.
[4] E. Dittert and M. J. O’Donnell, Lower bounds for sorting with realistic instruction sets,IEEE Trans. Comput.34, 4 (1985), pp. 311-317. · Zbl 0556.68030 · doi:10.1109/TC.1985.5009381
[5] D. P. Dobkin and R. Lipton, On the complexity of computations under varying sets of primitives,J. Comput. System Sci.18 (1979), pp. 86-91. · Zbl 0409.68023 · doi:10.1016/0022-0000(79)90054-0
[6] H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM J. Comput.15, 2 (1986), pp. 317-340. · Zbl 0602.68102 · doi:10.1137/0215023
[7] S. Even,Graph Algorithms, Computer Science Press, Potomac, MD, 1979. · Zbl 0441.68072
[8] I. Fary, On straight line representation of planar graphs,Acta Sci. Math. (Szeged)11 (1948), pp. 229-233. · Zbl 0030.17902
[9] L. Guibas, L. Ramshaw, and J. Stolfi, A kinetic framework for computational geometry,Proc. 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, pp. 100-111.
[10] J. Hong, On lower bounds of time complexity of some algorithms,Sci. Sinica22 (1979), pp. 890-900. · Zbl 0419.68084
[11] J. Hopcroft and R. Tarjan, Dividing a graph into triconnected components,SIAM J. Comput.2, 3 (1973), pp. 135-158. · Zbl 0281.68021 · doi:10.1137/0202012
[12] J. Hopcroft and R. Tarjan, Efficient planarity testing,J. ACM21, 4 (1974), pp. 549-568. · Zbl 0307.68025 · doi:10.1145/321850.321852
[13] D. G. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput.12, 1 (1983), pp. 28-35. · Zbl 0501.68034 · doi:10.1137/0212002
[14] D. E. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[15] D. T. Lee and F. P. Preparata, Location of a point in a planar subdivision and its applications,SIAM J. Comput.6, 1 (1977), pp. 594-606. · Zbl 0357.68034 · doi:10.1137/0206043
[16] Lempel, A.; Even, S.; Cederbaum, I.; Rosenstiehl, P. (ed.), An algorithm for planarity testing for graphs, International Symposium, Rome, July 1966, New York
[17] D. E. Muller and F. P. Preparata, Finding the intersection of two convex polyhedra,Theoret. Comput. Sci.7, 2 (1978), pp. 217-236. · Zbl 0396.52002 · doi:10.1016/0304-3975(78)90051-8
[18] W. J. Paul and J. Simon, Decision trees and random access machines,Symp. über Logic and Algorithmik, Zürich, 1980. · Zbl 0482.68044
[19] F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[20] R. E. Tarjan and C. J. Van Wyk, AnO(n log logn)-time algorithm for triangulating simple polygons, unpublished manuscript, 1986.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.