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 with m corners. We prove that it can be decided in O(mn) time if such a drawing exists. In the positive case, our algorithm also outputs such a drawing.
%0 Conference Paper
%1 aklss-obdog-eurocg20
%A Angelini, Patrizio
%A Kindermann, Philipp
%A Löffler, Andre
%A Schlipf, Lena
%A Symvonis, Antonios
%B Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)
%D 2020
%E Chaplick, Steven
%E Kindermann, Philipp
%E Wolff, Alexander
%I Würzburg
%K myown
%P 70:1--70:6
%T One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons
%U http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_70.pdf
%X 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 with m corners. We prove that it can be decided in O(mn) time if such a drawing exists. In the positive case, our algorithm also outputs such a drawing.
@inproceedings{aklss-obdog-eurocg20,
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 with m corners. We prove that it can be decided in O(mn) time if such a drawing exists. In the positive case, our algorithm also outputs such a drawing.},
added-at = {2021-02-12T10:20:51.000+0100},
author = {Angelini, Patrizio and Kindermann, Philipp and Löffler, Andre and Schlipf, Lena and Symvonis, Antonios},
biburl = {https://www.bibsonomy.org/bibtex/216ed846a7054102d2b14d07dc840bc02/kindermann},
booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)},
editor = {Chaplick, Steven and Kindermann, Philipp and Wolff, Alexander},
interhash = {f137f7a904a82120ff204f7aa9fc0b5a},
intrahash = {16ed846a7054102d2b14d07dc840bc02},
keywords = {myown},
note = {Abstract},
pages = {70:1--70:6},
publisher = {Würzburg},
timestamp = {2021-02-12T10:20:51.000+0100},
title = {One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons},
url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/papers/eurocg20_paper_70.pdf},
year = 2020
}