One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons

Abstract

We consider the problem of drawing an outerplanar graph with $n$ vertices with at most one bend per edge if the outer face is already drawn as a simple polygon. We prove that it can be decided in $O(nm)$ time if such a drawing exists, where $m\le n-3$ is the number of interior edges. In the positive case, we can also compute such a drawing.

Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)