2014/09/01 by Martin Nöllenburg, Nöllenburg, Martin, Roman Prutkin +3
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1409.0315
22 pages, 9 figures, full version of a paper appearing in Graph Drawing 2014. Compared to the previous version, contains a new result on area requirements of strongly monotone drawings
arxiv created 2014/12/04 · arxiv updated 2014/12/05
An st-path in a drawing of a graph is self-approaching if during the traversal of the corresponding curve from s to any point t' on the curve the distance to t' is non-increasing. A path has increasing chords if it is self-approaching in both directions. A drawing is self-approaching (increasing-chord) if any pair of vertices is connected by a self-approaching (increasing-chord) path. We study self-approaching and increasing-chord drawings of triangulations and 3-connected planar graphs. We show that in the Euclidean plane, triangulations admit increasing-chord drawings, and for planar 3-trees we can ensure planarity. We prove that strongly monotone (and thus increasing-chord) drawings of trees and binary cactuses require exponential resolution in the worst case, answering an open question by Kindermann et al. [GD'14]. Moreover, we provide a binary cactus that does not admit a self-approaching drawing. Finally, we show that 3-connected planar graphs admit increasing-chord drawings in the hyperbolic plane and characterize the trees that admit such drawings.