# 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