On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs

Nöllenburg, Martin and Prutkin, Roman and Rutter, Ignaz (2014) On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 476-487 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_40).

Full text not available from this repository.


An st-path in a drawing of a graph is self-approaching if during a 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. Moreover, we give 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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_40
Classifications:G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
Z Theory > Z.750 Topology
ID Code:1456

Repository Staff Only: item control page


Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V. Self-approaching Graphs. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 260-271

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

Angelini, P., Battista, G., Frati, F. (2012) Succinct greedy drawings do not always exist. Networks 59: pp. 267-274

Angelini, P., Didimo, W., Kobourov, S., Mchedlidze, T., Roselli, V., Symvonis, A., Wismath, S. Monotone drawings of graphs with fixed embedding. In: Speckmann, B. eds. (2012) Graph Drawing. Springer, Heidelberg, pp. 379-390

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

Dhandapani, R. (2010) Greedy drawings of triangulations. Discrete Comput. Geom. 43: pp. 375-392

Eppstein, D., Goodrich, M.T. (2011) Succinct greedy geometric routing using hyperbolic geometry. IEEE Trans. Computers 60: pp. 1571-1580

Felsner, S.: Geometric Graphs and Arrangements. Vieweg+Teubner Verlag (2004)

Goodrich, M.T., Strash, D. Succinct greedy geometric routing in the Euclidean plane. In: Dong, Y., Du, D.-Z., Ibarra, O. eds. (2009) Algorithms and Computation. Springer, Heidelberg, pp. 781-791

Huang, W., Eades, P., Hong, S.-H.: A graph reading behavior: Geodesic-path tendency. In: IEEE Pacific Visualization Symposium (PacificVis 2009), pp. 137–144 (2009)

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

Kleinberg, R.: Geographic routing using hyperbolic space. In: Computer Communications (INFOCOM 2007), pp. 1902–1909. IEEE (2007)

Moitra, A., Leighton, T. (2010) Some Results on Greedy Embeddings in Metric Spaces. Discrete Comput. Geom. 44: pp. 686-705

Nöllenburg, M., Prutkin, R. Euclidean greedy drawings of trees. In: Bodlaender, H.L., Italiano, G.F. eds. (2013) Algorithms – ESA 2013. Springer, Heidelberg, pp. 767-778

Nöllenburg, M., Prutkin, R., Rutter, I.: On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs. CoRR arXiv:1409.0315 (2014)

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

Purchase, H.C., Hamer, J., Nöllenburg, M., Kobourov, S.G. On the usability of Lombardi graph drawings. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 451-462

Rao, A., Ratnasamy, S., Papadimitriou, C., Shenker, S., Stoica, I.: Geographic routing without location information. In: Mobile Computing and Networking (MobiCom 2003), pp. 96–108. ACM (2003)

Rote, G. (1994) Curves with increasing chords. Math. Proc. Camb. Phil. Soc. 115: pp. 1-12

Schnyder, W.: Embedding planar graphs on the grid. In: Discrete Algorithms (SODA 1990), pp. 138–148. SIAM (1990)

Wang, J.-J., He, X. (2014) Succinct strictly convex greedy drawing of 3-connected plane graphs. Theor. Comput. Sci. 532: pp. 80-90