This paper introduces and studies the concept of a curve embedding of a planar graph. Let 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 C of 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.
Drawing Planar Graphs on a Curve
DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2003
Abstract
This paper introduces and studies the concept of a curve embedding of a planar graph. Let 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 C of 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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
