Abstract
Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing.
This research began at the Graph and Network Visualization Workshop 2019 (GNV’19) in Heiligkreuztal. S. C. is funded by the German Research Foundation DFG – Project-ID 50974019 – TRR 161 (B06). M. H. is supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681. S. K. is supported by NSF grants CCF-1740858, CCF-1712119, and DMS-1839274.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bodwin, G.: On the structure of unique shortest paths in graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp. 2071–2089. SIAM (2019). https://doi.org/10.1137/1.9781611975482.125
Frasser, C.E., Vostrov, G.N.: Geodetic graphs homeomorphic to a given geodetic graph. CoRR abs/1611.01873 (2016). http://arxiv.org/abs/1611.01873
Hoffman, A.J., Singleton, R.R.: Moore graphs with diameter 2 and 3. IBM J. Res. Dev. 5(4), 497–504 (1960). https://doi.org/10.1147/rd.45.0497
Hughes, D.R., Piper, F.C.: Projective Planes, Graduate Texts in Mathematics, vol. 6. Springer, New York (1973)
Kővári, T., Sós, V.T., Turán, P.: On a problem of K. Zarankiewicz. Colloq. Math. 3, 50–57 (1954). https://doi.org/10.4064/cm-3-1-50-57
Lee, D.T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14, 393–410 (1984). https://doi.org/10.1002/net.3230140304
Ore, Ø.: Theory of Graphs, Colloquium Publications, vol. 38. American Mathematical Society, Providence, RI (1962). https://doi.org/10.1090/coll/038
Pach, J., Tóth, G.: Which crossing number is it anyway? J. Combin. Theory Ser. B 80(2), 225–246 (2000). https://doi.org/10.1006/jctb.2000.1978
Parthasarathy, K.R., Srinivasan, N.: Some general constructions of geodetic blocks. J. Combin. Theory Ser. B 33(2), 121–136 (1982). https://doi.org/10.1016/0095-8956(82)90063-6
Plesník, J.: Two constructions of geodetic graphs. Math. Slovaca 27(1), 65–71 (1977). https://dml.cz/handle/10338.dmlcz/136134
Plesník, J.: A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs. J. Combin. Theory Ser. B 36(3), 284–297 (1984). https://doi.org/10.1016/0095-8956(84)90034-0
Scapellato, R.: Geodetic graphs of diameter two and some related structures. J. Combin. Theory Ser. B 41(2), 218–229 (1986). https://doi.org/10.1016/0095-8956(86)90045-6
Stemple, J.G.: Geodetic graphs homeomorphic to a complete graph. Ann. N. Y. Acad. Sci. 319(1), 512–517 (1979). https://doi.org/10.1111/j.1749-6632.1979.tb32829.x
Stemple, J.G., Watkins, M.E.: On planar geodetic graphs. J. Comb. Theory Ser. B 4(2), 101–117 (1968). https://doi.org/10.1016/S0021-9800(68)80035-3
Watkins, M.E.: A characterization of planar geodetic graphs. J. Comb. Theory 2(1), 102–103 (1967). https://doi.org/10.1016/S0021-9800(67)80118-2
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Cornelsen, S. et al. (2020). Drawing Shortest Paths in Geodetic Graphs. In: Auber, D., Valtr, P. (eds) Graph Drawing and Network Visualization. GD 2020. Lecture Notes in Computer Science(), vol 12590. Springer, Cham. https://doi.org/10.1007/978-3-030-68766-3_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-68766-3_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-68765-6
Online ISBN: 978-3-030-68766-3
eBook Packages: Computer ScienceComputer Science (R0)