Back to Search Start Over

One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons

Authors :
Angelini, Patrizio
Kindermann, Philipp
Löffler, Andre
Schlipf, Lena
Symvonis, Antonios
Publication Year :
2021

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.<br />Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2108.12321
Document Type :
Working Paper