Self-approaching Graphs

Alamdari, Soroush and Chan, Timothy M. and Grant, Elyot and Lubiw, Anna and Pathak, Vinayak (2013) Self-approaching Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 260-271(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.

Abstract

In this paper we introduce self-approaching graph drawings. A straight-line drawing of a graph is self-approaching if, for any origin vertex s and any destination vertex t, there is an st-path in the graph such that, for any point q on the path, as a point p moves continuously along the path from the origin to q, the Euclidean distance from p to q is always decreasing. This is a more stringent condition than a greedy drawing (where only the distance between vertices on the path and the destination vertex must decrease), and guarantees that the drawing is a 5.33-spanner. We study three topics: (1) recognizing self-approaching drawings; (2) constructing self-approaching drawings of a given graph; (3)constructing a self-approaching Steiner network connecting a given set of points. We show that: (1) there are efficient algorithms to test if a polygonal path is self-approaching in $ℝ^2$ and $ℝ^3$, but it is NP-hard to test if a given graph drawing in $ℝ^3$ has a self-approaching uv-path; (2) we can characterize the trees that have self-approaching drawings; (3) for any given set of terminal points in the plane, we can find a linear sized network that has a self-approaching path between any ordered pair of terminals.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-642-36763-2_23
Classifications:	P Styles > P.720 Straight-line Z Theory > Z.250 Geometry
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1315

Actions (login required)

View Item