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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1190

Actions (login required)

View Item View Item