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