On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs

Nöllenburg, Martin and Prutkin, Roman and Rutter, Ignaz (2014) On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 476-487(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_40).

Full text not available from this repository.

Abstract

An st-path in a drawing of a graph is self-approaching if during a 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. Moreover, we give 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_40
Classifications: G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
Z Theory > Z.750 Topology
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 21 May 2015 14:48
Last Modified: 21 May 2015 14:48
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1456

Actions (login required)

View Item View Item