Upward planar graphs and their duals ? ??
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 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.
upward planarity planar graphs dual graphs graph drawing surfaces