Constrained Point-Set Embeddability of Planar Graphs

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk and Wismath, Stephen (2009) Constrained Point-Set Embeddability of Planar Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 360-371 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_35).

Full text not available from this repository.

Abstract

This paper starts the investigation of a constrained version of the pointset embeddability problem. Let G = (V , E ) be a planar graph with n vertices, G′ = (V ′ , E ′ ) a subgraph of G, and S a set of n distinct points in the plane. We study the problem of computing a point-set embedding of G on S subject to the constraint that G′ is drawn with straight-line edges. Different drawing algorithms are presented that guarantee small curve complexity of the resulting drawing, i.e. a small number of bends per edge. It is proved that: (i) If G′ is an outerplanar graph and S is any set of points in convex position, a point-set embedding of G on S can be computed such that the edges of E \ E ′ have at most 4 bends each. (ii) If S is any set of points in general position and G′ is a face of G or if it is a simple path, the curve complexity of the edges of E \ E ′ is at most 8. (iii) If S is in general position and G′ is a set of k disjoint paths, the curve complexity of the edges of E \ E ′ is O(2k ).

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_35
Classifications:P Styles > P.720 Straight-line
P Styles > P.540 Planar
ID Code:922

Repository Staff Only: item control page

References

Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theoret. Comput. Sci. 408(2-3), 129-142(2008)

Bose, P.: On embedding an outer-planar graph on a point set. Comput. Geom. Theory Appl. 23, 303–312 (2002)

Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. J. Graph Algorithms Appl. 2(1), 1–15 (1997)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Trotta, F., Wismath, S.K.: k-colored point-set embeddability of outerplanar graphs. J. Graph Algorithms Appl. 11(1), 29–49 (2008)

Di Giacomo, E., Liotta, G., Trotta, F.: On embedding a graph on two sets of points. Internat. J. Found. Comput. Sci. 17(5), 1071–1094 (2006)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Point-set embeddings of trees with edge constraints. In: Hong, S.H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 113–124. Springer, Heidelberg (2008)

Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Comput. Geom. Theory Appl. 30(1), 1–23 (2005)

Di Giacomo, E., Liotta, G., Trotta, F.: Drawing colored graphs with constrained vertex positions and few bends per edge. In: Hong, S.H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 315–326. Springer, Heidelberg (2008)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly 98(2), 165–166 (1991)

Halton, J.H.: On the thickness of graphs of given degree. Inform. Sci. 54, 219–238 (1991)

Ikebe, Y., Perles, M., Tamura, A., Tokunaga, S.: The rooted tree embedding problem into points in the plane. Discrete Comput. Geom. 11, 51–63 (1994)

Kaneko, A., Kano, M.: Straight line embeddings of rooted star forests in the plane. Discrete Appl. Math. 101, 167–175 (2000)

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

Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl. 6(1), 115–129 (2002)

Pach, J., Törocsik, J.: Layout of rooted trees. Planar Graphs (DIMACS Series in Discrete Math. and Theoretical Comput. Sci.) 9, 131–137 (1993)

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

Sugiyama, K.: Graph Drawing and Applications for Software and Knowledge Engineers. Word Scientific (2002)