Home  Issues  About JGAA  Instructions for Authors 
"Special issue on Selected papers from the Twentyeighth International Symposium on Graph Drawing and Network Visualization, GD 2020"
DOI: 10.7155/jgaa.00598
Drawing Shortest Paths in Geodetic Graphs
Sabine Cornelsen,
Maximilian Pfister,
Henry FĂ¶rster,
Martin Gronemann,
Michael Hoffmann,
Stephen Kobourov, and
Thomas Schneck
Vol. 26, no. 3, pp. 353361, 2022. Regular paper.
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. On the positive side we show that geodetic graphs admit a philogeodetic drawing if both the diameter and the density are very low.
This work is licensed under the terms of the CCBY license.

Submitted: October 2020.
Reviewed: April 2022.
Revised: May 2022.
Accepted: May 2022.
Final: June 2022.
Published: June 2022.

Journal Supporters
