1. Curve-constrained drawings of planar graphs
- Author
-
Di Giacomo, Emilio, Didimo, Walter, Liotta, Giuseppe, and Wismath, Stephen K.
- Subjects
- *
CURVES , *GRAPHIC methods , *CONCAVE functions , *REAL variables - Abstract
Let
C be the family of 2D curves described by concave functions, letG be a planar graph, and letL be a linear ordering of the vertices ofG .L is a curve embedding ofG if for any given curveΛ∈C there exists a planar drawing ofG such that: (i) the vertices are constrained to be onΛ with the same ordering as inL , 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. [Copyright &y& Elsevier]- Published
- 2005
- Full Text
- View/download PDF