2026-07-22T13:29:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5929 2024-03-06T10:37:18Z ddc:004 open_access

Strongly Monotone Drawings of Planar Graphs Felsner, Stefan Igamberdiev, Alexander Kindermann, Philipp Klemz, Boris Mchedlidze, Tamara Scheucher, Manfred graph drawing planar graphs strongly monotone strictly convex primal-dual circle packing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Felsner and Alexander Igamberdiev and Philipp Kindermann and Boris Klemz and Tamara Mchedlidze and Manfred Scheucher 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.37 urn:nbn:de:0030-drops-59292 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.37 eng https://creativecommons.org/licenses/by/3.0/legalcode