Geodesic
Drawing Shortest Paths in Geodetic Graphs
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020 , Tome 26 (2022) no. 3, pp. 353-361.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00598
Keywords: edge crossings, unique shortest paths, geodetic graphs 
@article{JGAA_2022_26_3_a4,
     author = {Sabine Cornelsen and Maximilian Pfister and Henry F\"orster and Martin Gronemann and Michael Hoffmann and Stephen Kobourov and Thomas Schneck},
     title = {Drawing {Shortest} {Paths} in {Geodetic} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {353--361},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2022},
     doi = {10.7155/jgaa.00598},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00598/}
}
TY  - JOUR
AU  - Sabine Cornelsen
AU  - Maximilian Pfister
AU  - Henry Förster
AU  - Martin Gronemann
AU  - Michael Hoffmann
AU  - Stephen Kobourov
AU  - Thomas Schneck
TI  - Drawing Shortest Paths in Geodetic Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 353
EP  - 361
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00598/
DO  - 10.7155/jgaa.00598
LA  - en
ID  - JGAA_2022_26_3_a4
ER  - 
%0 Journal Article
%A Sabine Cornelsen
%A Maximilian Pfister
%A Henry Förster
%A Martin Gronemann
%A Michael Hoffmann
%A Stephen Kobourov
%A Thomas Schneck
%T Drawing Shortest Paths in Geodetic Graphs
%J Journal of Graph Algorithms and Applications
%D 2022
%P 353-361
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00598/
%R 10.7155/jgaa.00598
%G en
%F JGAA_2022_26_3_a4
Sabine Cornelsen; Maximilian Pfister; Henry Förster; Martin Gronemann; Michael Hoffmann; Stephen Kobourov; Thomas Schneck. Drawing Shortest Paths in Geodetic Graphs. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020
					, Tome 26 (2022) no. 3, pp. 353-361. doi : 10.7155/jgaa.00598. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00598/

Cité par Sources :