Curve-constrained drawings of planar graphs (Q706719)

The authors study 2D-drawings of graphs where the vertices are constrained to be on a given curve and the edges have at most one bend. Introducing the concept of a curve embedding of a planar graph, they prove that every planar graph admits a curve embedding and presents a linear-time algorithm to compute one [cf. \textit{F. Bernhart} and \textit{P. C. Kainen}, J. Comb. Theory, Ser. B 27, 320--331 (1979; Zbl 0427.05028)]. Interplay between curve embeddings and upward drawings is also studied. Curve embeddings are also used to simplify and extend the algorithm of \textit{M. Kaufmann} and \textit{R. Wiese} [J. Graph Algorithms Appl. 6, 115--129 (2002; Zbl 0999.68164)] for point set embeddability.