Upward Geometric Graph Embeddings into Point Sets

Angelini, Patrizio and Frati, Fabrizio and Geyer, Markus and Kaufmann, Michael and Mchedlidze, Tamara and Symvonis, Antonios (2011) Upward Geometric Graph Embeddings into Point Sets. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 25-37 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_3).

Full text not available from this repository.

Abstract

We study the problem of characterizing the directed graphs with an upward straight-line embedding into every point set in general or in convex position. We solve two questions posed by Binucci et al. [Computational Geometry: Theory and Applications, 2010]. Namely, we prove that the classes of directed graphs with an upward straight-line embedding into every point set in convex position and with an upward straight-line embedding into every point set in general position do not coincide, and we prove that every directed caterpillar admits an upward straight-line embedding into every point set in convex position. Further, we provide new partial positive results on the problem of constructing upward straight-line embeddings of directed paths into point sets in general position.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_3
Classifications:G Algorithms and Complexity > G.490 Embeddings
P Styles > P.840 Upward
ID Code:1190

Repository Staff Only: item control page

References

Angelini, P., Frati, F., Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward geometric graph embeddings into point sets. Tech. Report 177, Dipartimento di Informatica e Automazione, Università Roma Tre (2010)

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

Binucci, C., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S., Liotta, G.: Upward straight-line embeddings of directed graphs into point sets. Computat. Geom. Th. Appl. 43, 219–232 (2010)

Bose, P.: On embedding an outer-planar graph in a point set. Computat. Geom. Th. Appl. 23(3), 303–312 (2002)

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

Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Alg. Appl. 10(2), 353–366 (2006)

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

Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A.: Computing upward topological book embeddings of upward planar digraphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 172–183. Springer, Heidelberg (2007)

Gritzmann, P., Pach, B.M.J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Mont. 98, 165–166 (1991)

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

Wiegers, M.: Recognizing outerplanar graphs in linear time. In: Tinhofer, G., Schmidt, G. (eds.) WG 1986. LNCS, vol. 246, pp. 165–176. Springer, Heidelberg (1987)