M. Nöllenburg, R. Prutkin, I. Rutter:

"On Self-Approaching And Increasing-Chord Drawings Of 3-Connected Planar Graphs";

Journal of Computational Geometry,7(2016), 1; S. 47 - 69.

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 t0 on the curve the distance to t0 is nonincreasing.

A path is increasing-chord 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. [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.

http://publik.tuwien.ac.at/files/PubDat_249244.pdf

Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.