Drawing shortest paths in geodetic graphs. (English) Zbl 07436628
Auber, David (ed.) et al., Graph drawing and network visualization. 28th international symposium, GD 2020, Vancouver, BC, Canada, September 16–18, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12590, 333-340 (2020).
Summary: 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.
For the entire collection see [Zbl 1475.68017].
For the entire collection see [Zbl 1475.68017].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Ore, Ø.: Theory of Graphs, Colloquium Publications, vol. 38. American Mathematical Society, Providence, RI (1962). https://doi.org/10.1090/coll/038 · Zbl 0105.35401 |
| [2] | Hughes, D.R., Piper, F.C.: Projective Planes, Graduate Texts in Mathematics, vol. 6. Springer, New York (1973) · Zbl 0267.50018 |
| [3] | 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 |
| [4] | 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 · Zbl 1434.05079 |
| [5] | 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 · Zbl 0096.38102 · doi:10.1147/rd.45.0497 |
| [6] | 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 · Zbl 0545.90098 · doi:10.1002/net.3230140304 |
| [7] | 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 · Zbl 1023.05042 · doi:10.1006/jctb.2000.1978 |
| [8] | 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 · Zbl 0488.05056 · doi:10.1016/0095-8956(82)90063-6 |
| [9] | Plesník, J.: Two constructions of geodetic graphs. Math. Slovaca 27(1), 65-71 (1977). https://dml.cz/handle/10338.dmlcz/136134 · Zbl 0347.05113 |
| [10] | 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 · Zbl 0527.05043 · doi:10.1016/0095-8956(84)90034-0 |
| [11] | 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 · Zbl 0576.05038 · doi:10.1016/0095-8956(86)90045-6 |
| [12] | 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 · Zbl 0481.05057 · doi:10.1111/j.1749-6632.1979.tb32829.x |
| [13] | 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 · Zbl 0153.54004 · doi:10.1016/S0021-9800(68)80035-3 |
| [14] | Watkins, M.E.: A characterization of planar geodetic graphs. J. Comb. Theory 2(1), 102-103 (1967). https://doi.org/10 · Zbl 0148.17801 · doi:10.1016/S0021-9800(67)80118-2 |
| [15] | 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 · Zbl 0055.00704 · doi:10.4064/cm-3-1-50-57 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
