2012 | OriginalPaper | Buchkapitel
Classification of Planar Upward Embedding
verfasst von : Christopher Auer, Christian Bachmaier, Franz Josef Brandenburg, Andreas Gleißner
Erschienen in: Graph Drawing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 ℝ
3
and introduces new classes of planar upward drawable graphs, where some of them even allow cycles. Our approach leads to a classification 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.