Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.37
URN: urn:nbn:de:0030-drops-59292
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5929/
Felsner, Stefan ; Igamberdiev, Alexander ; Kindermann, Philipp ; Klemz, Boris ; Mchedlidze, Tamara ; Scheucher, Manfred
Strongly Monotone Drawings of Planar Graphs
| pdf-format: |
|
Abstract
A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices.We present algorithms to compute crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.
BibTeX - Entry
@InProceedings{felsner_et_al:LIPIcs:2016:5929,
author = {Stefan Felsner and Alexander Igamberdiev and Philipp Kindermann and Boris Klemz and Tamara Mchedlidze and Manfred Scheucher},
title = {{Strongly Monotone Drawings of Planar Graphs}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {37:1--37:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5929},
URN = {urn:nbn:de:0030-drops-59292},
doi = {10.4230/LIPIcs.SoCG.2016.37},
annote = {Keywords: graph drawing, planar graphs, strongly monotone, strictly convex, primal-dual circle packing}
}
| Keywords: | graph drawing, planar graphs, strongly monotone, strictly convex, primal-dual circle packing | |
| Seminar: | 32nd International Symposium on Computational Geometry (SoCG 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 10.06.2016 |
