Titel: | Strongly Monotone Drawings of Planar Graphs |
---|---|
AutorInnen: |
Stefan Felsner
Alexander Igamberdiev Philipp Kindermann Boris Klemz Tamara Mchedlidze Manfred Scheucher |
Kategorie: | Konferenzbandbeiträge |
erschienen in: | Proceedings of the 32nd International Symposium on Computational Geometry (SoCG'16), pp. 37:1--37:15 |
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. |
Download: | Proceeding Website |
BibTeX-Eintrag: | @InProceedings{fikkms-smdpg-socg16, Title = {Strongly Monotone Drawings of Planar Graphs}, Author = {Stefan Felsner and Alexander Igamberdiev and Philipp Kindermann and Boris Klemz and Tamara Mchedlidze and Manfred Scheucher}, Booktitle = {Proceedings of the 32nd International Symposium on Computational Geometry (SoCG'16)}, Year = {2016}, Editor = {S{\'a}ndor Fekete and Anna Lubiw}, Pages = {37:1--37:15}, Series = {LIPIcs}, Abstract = {A straight-line drawing of a graph is a \emph{monotone drawing} if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a \emph{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.}, Doi = {10.4230/LIPIcs.SoCG.2016.37} } |