Point-Set Embedding of Trees with Edge Constraints

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2008) Point-Set Embedding of Trees with Edge Constraints. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 113-124 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_14).

Full text not available from this repository.

Abstract

Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding$ of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph G' subset G on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of G'. We concentrate on trees and show how to compute the output in O(n^2 log n) time and with at most 1 + 2 lceil k/2 rceil bends per edge, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least k-3 bends for some of the edges.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_14
Classifications:M Methods > M.900 Tree
G Algorithms and Complexity > G.490 Embeddings
ID Code:833

Repository Staff Only: item control page

References

M. Badent, E. Di Giacomo, and G. Liotta. Drawing colored graphs on colored points. In Proceedings of the Tenth Workshop on Algorithms and Data Structures, WADS 2007, Lecture Notes Computer Science. Springer-Verlag.

P. Bose. On embedding an outer-planar graph on a point set. Computational Geometry: Theory and Applications, 23:303-312. 2002.

P. Bose, M. McAllister, and J. Snoeyink. Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications, 2(1):1-15, 1997.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

E. Di Giacomo, W. Didimo, G. Liotta, H. Meijer, F. Trotta, and S. K. Wismath. k-colored point-set embeddability of outerplanar graphs. In Graph Drawing (Proc. GD 2006), volume 4372 of LNCS, pages 318-329. Springer-Verlag, 2007.

E. Di Giacomo, G. Liotta, and F. Trotta. On embedding a graph on two sets of points. International Journal of Foundations of Computer Science, Special Issue on Graph Drawing, 17(5):1071-1094, 2006.

J. H. Halton. On the thickness of graphs of given degree. Information Sciences, 54:219-238, 1991.

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

A. Kaneko and M. Kano. Straight line embeddings of rooted star forests in the plane. Discrete Appl. Mathematics, 101:167-175, 2000.

A. Kaneko and M. Kano. Semi-balanced partitions of two sets of points and embeddings of rooted forests. Int. J. Comput. Geom. Appl., 15(3):229-238, 2005.

M. Kaufmann and D. Wagner, editors. Drawing Graphs, volume 2025 of Lecture Notes in Computer Science. Springer-Verlag, 2001.

M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

T. Nishizeki and M. S. Rahman. Planar Graph Drawing, volume 12 of Lecture Notes Series on Computing. World Scientific, 2004.

J. O' Rourke. Art Gallery Theorems and Algorithms. Oxford Univ. Press, 1987.

J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics, 17:717-728, 2001.

M. Patrignani. On extending a partial straight-line drawing. International Journal of Foundations of Computer Science, Special Issue on Graph Drawing, 17(5):1061-1069, 2006.

F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 3rd edition, Oct. 1990.