Selfapproaching GraphsAlamdari, Soroush and Chan, Timothy M. and Grant, Elyot and Lubiw, Anna and Pathak, Vinayak (2013) Selfapproaching Graphs. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 260271(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractIn this paper we introduce selfapproaching graph drawings. A straightline drawing of a graph is selfapproaching if, for any origin vertex s and any destination vertex t, there is an stpath 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.33spanner. We study three topics: (1) recognizing selfapproaching drawings; (2) constructing selfapproaching drawings of a given graph; (3)constructing a selfapproaching Steiner network connecting a given set of points. We show that: (1) there are efficient algorithms to test if a polygonal path is selfapproaching in $ℝ^2$ and $ℝ^3$, but it is NPhard to test if a given graph drawing in $ℝ^3$ has a selfapproaching uvpath; (2) we can characterize the trees that have selfapproaching drawings; (3) for any given set of terminal points in the plane, we can find a linear sized network that has a selfapproaching path between any ordered pair of terminals.
Actions (login required)
