Back to Search
Start Over
One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons
- 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)
- Subjects :
- Computer Science - Computational Geometry
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2108.12321
- Document Type :
- Working Paper