TY - GEN

T1 - Self-approaching graphs

AU - Alamdari, Soroush

AU - Chan, Timothy M.

AU - Grant, Elyot

AU - Lubiw, Anna

AU - Pathak, Vinayak

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - graph drawing

KW - increasing-chord

KW - self-approaching

UR - http://www.scopus.com/inward/record.url?scp=84874173553&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84874173553&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36763-2_23

DO - 10.1007/978-3-642-36763-2_23

M3 - Conference contribution

AN - SCOPUS:84874173553

SN - 9783642367625

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 260

EP - 271

BT - Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers

T2 - 20th International Symposium on Graph Drawing, GD 2012

Y2 - 19 September 2012 through 21 September 2012

ER -