Curve-constrained drawings of planar graphs

Let <f>C</f> be the family of 2D curves described by concave functions, let <f>G</f> be a planar graph, and let <f>L</f> be a linear ordering of the vertices of <f>G</f>. <f>L</f> is a curve embedding of <f>G</f> if for any given curve <f>Λ∈C</f> there exists a planar drawing of <f>G</f> such that: (i) the vertices are constrained to be on <f>Λ</f> with the same ordering as in <f>L</f>, 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]