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′ ⊂ 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 logn) time and with at most 1 + 2 ⌈k/2 ⌉ 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.
Research partially supported by the MIUR Project “MAINSTREAM: Algorithms for massive information structures and data streams” and by NSERC.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. In: WADS 2007. LNCS, Springer, Heidelberg (2007)
Bose, P.: On embedding an outer-planar graph on a point set. Computational Geometry: Theory and Applications 23, 303–312 (2002)
Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications 2(1), 1–15 (1997)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall, Upper Saddle River (1999)
Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Trotta, F., Wismath, S.K.: k-colored point-set embeddability of outerplanar graphs. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 318–329. Springer, Heidelberg (2007)
Di Giacomo, E., Liotta, G., Trotta, F.: 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)
Halton, J.H.: On the thickness of graphs of given degree. Information Sciences 54, 219–238 (1991)
Ikebe, Y., Perles, M., Tamura, A., Tokunaga, S.: The rooted tree embedding problem into points in the plane. Discrete Comput. Geometry 11, 51–63 (1994)
Kaneko, A., Kano, M.: Straight line embeddings of rooted star forests in the plane. Discrete Appl. Mathematics 101, 167–175 (2000)
Kaneko, A., Kano, M.: Semi-balanced partitions of two sets of points and embeddings of rooted forests. Int. J. Comput. Geom. Appl. 15(3), 229–238 (2005)
Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)
Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications 6(1), 115–129 (2002)
Nishizeki, T., Rahman, M.S.: Planar Graph Drawing. Lecture Notes Series on Computing, vol. 12. World Scientific, Singapore (2004)
O’Rourke, J.: Art Gallery Theorems and Algorithms. Oxford Univ. Press, Oxford (1987)
Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17, 717–728 (2001)
Patrignani, M.: On extending a partial straight-line drawing. International Journal of Foundations of Computer Science, Special Issue on Graph Drawing 17(5), 1061–1069 (2006)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, 3rd edn. Springer, Heidelberg (1990)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S. (2008). Point-Set Embedding of Trees with Edge Constraints . In: Hong, SH., Nishizeki, T., Quan, W. (eds) Graph Drawing. GD 2007. Lecture Notes in Computer Science, vol 4875. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77537-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-77537-9_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77536-2
Online ISBN: 978-3-540-77537-9
eBook Packages: Computer ScienceComputer Science (R0)