on self-approaching and increasing-chord drawings of 3-connected planar graphs
Article Quality & Performance Metrics
Abstract
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 2014). 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.
| Reference Key |
nllenburg2016journalon
Use this key to autocite in the manuscript while using
SciMatic Manuscript Manager or Thesis Manager
|
|---|---|
| Authors | ;Martin Nöllenburg;Roman Prutkin;Ignaz Rutter |
| Journal | canadian journal of infectious diseases and medical microbiology |
| Year | 2016 |
| DOI |
10.20382/jocg.v7i1a3
|
| URL | |
| Keywords |
Citations
No citations found. To add a citation, contact the admin at info@scimatic.org
Comments
No comments yet. Be the first to comment on this article.