On the Curve Complexity of Upward Planar Drawings

Brandenburg, F. J.

We consider directed graphs with an upward planar drawing on the plane, the sphere, the standing and the rolling cylinders. In general, the drawings allow complex curves for the edges with many zigzags and windings around the cylinder and the sphere. The drawings are simplified to polyline drawings with geodesics as straight segments and vertices and bends at grid points. On the standing cylinder the drawings have at most two bends per edge and no windings of edges around the cylinder. On the rolling cylinder edges may have one winding and five bends, and there are graphs where edges must wind. The drawings have a discrete description of linear size. The simplifications can be computed efficiently in O (� n^3 ) time, where ⌧ is the cost of computing the point of intersection of a curve and a horizontal line through a vertex. The time complexity does not depend on the description complexity of the drawing and its curves, but only on O(n^3) sample points.

Cite as: Brandenburg, F. J. (2012). On the Curve Complexity of Upward Planar Drawings. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 27-36

(from crpit.com) (local if available)