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, Redmond, WA, USA , pp. 260-271 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_23).

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
ID Code:1315

Repository Staff Only: item control page

References

Angelini, P., Colasante, E., Battista, G.D., Frati, F., Patrignani, M.: Monotone drawings of graphs. J. Graph Algorithms Appl. 16(1), 5–35 (2012)

Angelini, P., Didimo, W., Kobourov, S., Mchedlidze, T., Roselli, V., Symvonis, A., Wismath, S.: Monotone Drawings of Graphs with Fixed Embedding. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 379–390. Springer, Heidelberg (2012)

Angelini, P., Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl. 14(1), 19–51 (2010)

Aronov, B., de Berg, M., Cheong, O., Gudmundsson, J., Haverkort, H., Smid, M., Vigneron, A.: Sparse geometric graphs with small dilation. Computational Geometry 40(3), 207–219 (2008)

Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 15th ACM Symposium on Theory of Computing, New York, pp. 80–86 (1983)

Borradaile, G., Eppstein, D.: Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets. In: Proceedings of the 24th Annual Canadian Conference on Computational Geometry, CCCG, Charlottetown, PEI, Canada (2012)

Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S.: Competitive routing in the half-θ 6-graph. In: Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1319–1328 (2012)

Bose, P., Morin, P.: Online routing in triangulations. SIAM J. Comput. 33(4), 937–951 (2004)

Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67–90 (1995)

Chan, T.M.: Well-separated pair decomposition in linear time? Inform. Process. Lett. 107, 138–141 (2008)

Chin, F.Y.L., Guo, Z., Sun, H.: Minimum Manhattan network is NP-complete. Discrete & Computational Geometry 45(4), 701–722 (2011)

Dumitrescu, A., Tóth, C.D.: Light orthogonal networks with constant geometric dilation. Journal of Discrete Algorithms 7(1), 112–129 (2009)

Ebbers-Baumann, A., Grune, A., Klein, R.: The geometric dilation of finite point sets. Algorithmica 44, 137–149 (2006)

Ebbers-Baumann, A., Grüne, A., Klein, R., Karpinski, M., Knauer, C., Lingas, A.: Embedding point sets into plane graphs of small dilation. Int. J. Comput. Geometry Appl. 17(3), 201–230 (2007)

Eppstein, D.: Spanning trees and spanners. In: Sack, J., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425–461. North-Holland (2000)

Giannopoulos, P., Klein, R., Knauer, C., Kutz, M., Marx, D.: Computing geometric minimum-dilation graphs is NP-hard. Int. J. Comput. Geometry Appl. 20(2), 147–173 (2010)

Goodrich, M.T., Strash, D.: Succinct Greedy Geometric Routing in the Euclidean Plane. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 781–791. Springer, Heidelberg (2009)

Gudmundsson, J., Knauer, C.: Dilation and detour in geometric networks. In: Gonzalez, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC Press (2007)

Gudmundsson, J., Klein, O., Knauer, C., Smid, M.: Small Manhattan networks and algorithmic applications for the earth mover’s distance. In: Proc. 23rd European Workshop on Computational Geometry, pp. 174–177 (2007)

Har-Peled, S.: Geometric Approximation Algorithms. AMS (2011)

He, X., Zhang, H.: On succinct convex greedy drawing of 3-connected plane graphs. In: Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 1477–1486 (2011)

Icking, C., Klein, R., Langetepe, E.: Self-approaching curves. Math. Proc. Camb. Phil. Soc. 125, 441–453 (1995)

Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. Discrete and Computational Geometry 44, 686–705 (2010)

Moitra, A.: A solution to the Papadimitriou-Ratajczak conjecture. Master’s thesis, Massachusetts Institute of Technology (2009)

Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press (2007)

Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theor. Comput. Sci. 344, 3–14 (2005)

Rao, A., Ratnasamy, S., Papadimitriou, C., Shenker, S., Stoica, I.: Geographic routing without location information. In: Proc. 9th International Conference on Mobile Computing and Networking, pp. 96–108 (2003)

Rote, G.: Curves with increasing chords. Mathematical Proceedings of the Cambridge Philosophical Society 115, 1–12 (1994)

Wulff-Nilsen, C.: Computing the maximum detour of a plane geometric graph in subquadratic time. Journal of Computational Geometry 1(1), 101–122 (2010)

Xia, G.: Improved upper bound on the stretch factor of Delaunay triangulations. In: Proc. 27th ACM Symposium on Computational Geometry, pp. 264–273 (2011)