TY - GEN

T1 - Drawing Shortest Paths in Geodetic Graphs

AU - Cornelsen, Sabine

AU - Pfister, Maximilian

AU - Förster, Henry

AU - Gronemann, Martin

AU - Hoffmann, Michael

AU - Kobourov, Stephen

AU - Schneck, Thomas

N1 - Funding Information:
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.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2020

Y1 - 2020

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

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

KW - Edge crossings

KW - Geodetic graphs

KW - Unique shortest paths

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

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

U2 - 10.1007/978-3-030-68766-3_26

DO - 10.1007/978-3-030-68766-3_26

M3 - Conference contribution

AN - SCOPUS:85102745745

SN - 9783030687656

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

SP - 333

EP - 340

BT - Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Revised Selected Papers

A2 - Auber, David

A2 - Valtr, Pavel

PB - Springer Science and Business Media Deutschland GmbH

T2 - 28th International Symposium on Graph Drawing and Network Visualization, GD 2020

Y2 - 16 September 2020 through 18 September 2020

ER -