One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons
Angelini, Patrizio
Kindermann, Philipp Löffler, Andre Schlipf, Lena Symvonis, Antonios
Kindermann, Philipp
Löffler, Andre
Schlipf, Lena
Symvonis, Antonios
Citations
Altmetric:
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 ≤ n − 3 is the number of interior edges. In the positive case, we can also compute such a drawing.
Description
Date
2021
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Partial embedding, Outerplanar graphs, Visibility graph
Citation
Angelini, Patrizio, Philipp Kindermann, Andre Löffler, Lena Schlipf, and Antonios Symvonis. “One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons”. In Graph drawing and network visualization: 29th International Symposium, GD 2021, Tübingen, Germany, September 14-17, 2021, Revised selected papers, 184-192. Cham, Switzerland: Springer. 2021.