Classification of Planar Upward Embedding

Auer, Christopher and Bachmaier, Christian and Brandenburg, Franz Josef and Gleißner, Andreas (2012) Classification of Planar Upward Embedding. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 415-426(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_39).

Full text not available from this repository.

Abstract

We consider planar upward drawings of directed graphs on arbitrary surfaces where the upward direction is defined by a vector field. This generalizes earlier approaches using surfaces with a fixed embedding in R3 and introduces new classes of planar upward drawable graphs, where some of them even allow cycles. Our approach leads to a classifi- cation of planar upward embeddability. In particular, we show the coincidence of the classes of planar upward drawable graphs on the sphere and on the standing cylinder. These classes coincide with the classes of planar upward drawable graphs with a homogeneous field on a cylinder and with a radial field in the plane. A cyclic field in the plane introduces the new class RUP of upward drawable graphs, which can be embedded on a rolling cylinder. We establish strict inclusions for planar upward drawability on the plane, the sphere, the rolling cylinder, and the torus, even for acyclic graphs. Finally, upward drawability remains NP-hard for the standing cylinder and the torus; for the cylinder this was left as an open problem by Limaye et al.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_39
Classifications: G Algorithms and Complexity > G.490 Embeddings
P Styles > P.840 Upward
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1274

Actions (login required)

View Item View Item