ICS Theory Group

ICS 269, Fall 2004: Theory Seminar

22 Oct 2004:
Drawing Planar Graphs on a Curve
E. Di Giacomo, W. Didimo, G. Liotta, and S.K. Wismath
Speaker: Jeremy Yu Meng

This paper introduces and studies the concept of a curve embedding of a planar graph. Let C be the family of 2D curves described by concave functions and let G be a planar graph. A curve embedding of G is a linear ordering of the vertices of G such that there exists a crossing-free 2D drawing of G where the vertices are constrained to be on any given curve of C and the edges are drawn as polylines with at most one bend. We prove that every planar graph has a curve embedding which can be computed in linear time. Further we present applications of the concept of curve embedding to upward drawings and point-set constrained drawings.

From WG 2003 29th Workshop on Graph Theoretic Concepts in Computer Science, LNCS 2880