[Zurück]


Zeitschriftenartikel:

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.



Kurzfassung englisch:
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.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_249244.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.