Let $\cal C$ be the family of 2D curves described by concave functions, let $G$ be a planar graph, and let $L$ be a linear ordering of the vertices of $G$. $L$ is a {\em curve embedding} of $G$ if for any given curve $\Lambda \in {\cal C}$ there exists a planar drawing of $G$ such that: (i) the vertices are constrained to be on ${\Lambda}$ with the same ordering as in $L$, and (ii) the edges are polylines with at most one bend. Informally speaking, a curve embedding can be regarded as a two-page book embedding in which the spine is bent. Although deciding whether a graph has a two-page book embedding is an NP-hard problem, in this paper it is proven that every planar graph has a curve embedding which can be computed in linear time. Applications of the concept of curve embedding to upward drawability and point-set embeddability problems are also presented.
Curve-Constrained Drawings of Planar Graphs
DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2005
Abstract
Let $\cal C$ be the family of 2D curves described by concave functions, let $G$ be a planar graph, and let $L$ be a linear ordering of the vertices of $G$. $L$ is a {\em curve embedding} of $G$ if for any given curve $\Lambda \in {\cal C}$ there exists a planar drawing of $G$ such that: (i) the vertices are constrained to be on ${\Lambda}$ with the same ordering as in $L$, and (ii) the edges are polylines with at most one bend. Informally speaking, a curve embedding can be regarded as a two-page book embedding in which the spine is bent. Although deciding whether a graph has a two-page book embedding is an NP-hard problem, in this paper it is proven that every planar graph has a curve embedding which can be computed in linear time. Applications of the concept of curve embedding to upward drawability and point-set embeddability problems are also presented.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
