Upward planar graphs and their duals

Autor: Christian Bachmaier, Kathrin Hanauer, Christopher Auer, Franz J. Brandenburg, Andreas Gleißner
Rok vydání: 2015
Předmět:
Zdroj: Theoretical Computer Science. 571:36-49
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2015.01.003
Popis: We consider upward planar drawings of directed graphs in the plane (UP), and on standing (SUP) and rolling cylinders (RUP). In the plane and on the standing cylinder the edge curves are monotonically increasing in y-direction. On the rolling cylinder they wind unidirectionally around the cylinder. There is a strict hierarchy of classes of upward planar graphs: UP ? SUP ? RUP .In this paper, we show that rolling and standing cylinders switch roles when considering an upward planar graph and its dual. In particular, we prove that a strongly connected graph is RUP if and only if its dual is a SUP dipole. A dipole is an acyclic graph with a single source and a single sink. All RUP graphs are characterized in terms of their duals using generalized dipoles. Moreover, we obtain a characterization of the primals and duals of wSUP graphs which are upward planar graphs on the standing cylinder and allow for horizontal edge curves.
Databáze: OpenAIRE
Externí odkaz: