Logo

Login

On Embedding an Outer-Planar Graph in a Point Set

Bose, Prosenjit (1998) On Embedding an Outer-Planar Graph in a Point Set. [Conference Paper]

Full text not available from this repository.

Abstract

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(n log³ n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [GMPP91, CU96] that requires O(n²) time. Our algorithm is near-optimal as there is an \Omega (n log n) lower bound for the problem [BMS95]. We present a simpler O(nd) time and an O(n) space algorithm to compute a straight-line embedding of G in P where log n \leq d \leq 2n is the lenght of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(n log n) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal \theta (n log n) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.

Item Type:Conference Paper
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.490 Embeddings
M Methods > M.600 Planar
ID Code:175
Deposited By:Martinez Leon, Victoria
Deposited On:26 Oct 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

[BDLL95] P. Bose, G. Di Battista, W. Lenhart, and G. Liotta. Proximity constraints and representable trees. In R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. Gd '94), volume 894 of Lecture Notes in Computer Science, pages 340-351. Springer-Verlag, 1995.

[BLL96] P. Bose, W. Lenhart, and G. Liotta. Characterizing proximity trees. Algorithmica, 16:83-110, 1996.

[BM76] J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. Elsevier Science, New York, NY, 1976.

[BMS95] P. Bose, M. McAllister, and J. Snoeyink. Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications, to appear. Also appears in Proceedings of Graph Drawing GD `95, LNCS 1027, pp. 64-75, 1995.

[Cha85] B. Chazelle. On the convex layers of a planar set. IEEE Trans. on Inf. Theory, IT-31:509-517, 1985.

[CLR90] T. Cormen, C. Leiserson, and R. Rivest. Introduction to algorithms. MIT Press, Cambridge, Mass., 1990.

[CP95] P. Crescenzi and A. Piperno. Optinal-area upward drawings of AVL trees. In R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. Gd '94), volume 894 of Lecture Notes in Computer Science, pages 307-317. Springer-Verlag, 1995.

[CU96] N. Castaneda and J. Urrutia. Straight line embeddings of planar grahs on point sets. In Proc. Eighth Canadian Conf. on Comp. Geom., pages 312-318, 1996.

[DETT94] G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. Theory Appl., 4:235-282, 1994.

[EW94] P. Eades and S. Whitesides. The realization problem for Euclidean minimum spanning trees is NP-hard. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 49-56, 1994.

[Far48] I. Fary. On straight line representation of planar graphs. Acta Sci. Math. Szeged, 11:229-233, 1948.

[GMPP91] P. Gritzmann, B. Mohar, J. Pach and R. Pollack. Embedding a planar triangulation with vertices at specified points (solution to problem e3341) American Mathematical Monthly, 98:165-166, 1991.

[HS92] John Hershberger and Subhash Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32:249-267, 1992.

[IPTT94) Y. Ikebe, M. Perles, A. Tamura, and S. Tokunaga. The rooted tree embedding problem into points in the plane. Discrete & Computational Geometry, 11:51-63, 1994.

[KLTT93] G. Kant, G. Liotta, R. Tamassia, and I. Tollis. Area requirement of visibility representations of trees. In Proc. 5th Canad. Conf. Comput. Geom., pages 192-197, Waterloo, Canada, 1993.

[MA88] J. Manning and M.J. Atallah. Fast detection and display of symmetry in trees. Congressus Numerantium, 64:159-169, 1988.

[MS91] C. Monma and S. Suri. Transitions in geometric minimum spanning trees. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 239-249, 1991.

[OvL81]M. Overmars and J. van Leeuwen. Maintenance of cnfigurations in the plane. Journal of Computer and System Sciences, 23:166-204, 1981.

[PS85] F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, NY, 1985.

[PT93] Janós Pach and Jenö Töröcsik. Layout of rooted trees. In W.T. Trotter, editor, Planar Graphs, volume 9 of DIMACS Series, pages 131-137. American Mathematical Society, 1993.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.