A new algorithm for embedding plane graphs at fixed vertex locations (Q2121749)

This paper studies the problem of embedding a plane graph at pre-assigned fixed vertex locations with at most \(2.5n+1\) bends allowed per edge where \(n\) is the number of vertices of the graph. The complexity of the drawing is measured by the number of bends, two straight lines are joined at bends and a single straight line is 0-bend. The proposed algorithm improves the result by \textit{J. Pach} and \textit{R. Wenger} [Graphs Comb. 17, No. 4, 717--728 (2001; Zbl 0991.05036)], where the upper bound on the number of bends was \(24(n+2)\). Moreover, the proposed algorithm is extended to grid embeddings, orthogonal embeddings, and min-length embeddings. The time complexity of the proposed approach is quadratic.