Curve-constrained drawings of planar graphs

Let 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 curve embedding of G if for any given curve Λ∈C there exists a planar drawing of G such that: (i) the vertices are constrained to be on Λ 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.