Geodesic
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 589-606.

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

Given a set of terminal pairs on the external face of an undirected unweighted planar graph, we give a linear-time algorithm for computing the union of non-crossing shortest paths joining each terminal pair, if such paths exist. This allows us to compute distances between each terminal pair, within the same time bound. We also give a novel concept of incremental shortest path subgraph of a planar graph, i.e., a partition of the planar embedding in subregions that preserve distances, that can be of interest itself.
DOI : 10.7155/jgaa.00610
Keywords: planar graphs, non-crossing paths, shortest paths, undirected unweighted graphs 
@article{JGAA_2022_26_4_a8,
     author = {Lorenzo Balzotti and Paolo Franciosa},
     title = {Non-Crossing {Shortest} {Paths} in {Undirected} {Unweighted} {Planar} {Graphs} in {Linear} {Time}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {589--606},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2022},
     doi = {10.7155/jgaa.00610},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00610/}
}
TY  - JOUR
AU  - Lorenzo Balzotti
AU  - Paolo Franciosa
TI  - Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 589
EP  - 606
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00610/
DO  - 10.7155/jgaa.00610
LA  - en
ID  - JGAA_2022_26_4_a8
ER  - 
%0 Journal Article
%A Lorenzo Balzotti
%A Paolo Franciosa
%T Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
%J Journal of Graph Algorithms and Applications
%D 2022
%P 589-606
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00610/
%R 10.7155/jgaa.00610
%G en
%F JGAA_2022_26_4_a8
Lorenzo Balzotti; Paolo Franciosa. Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 589-606. doi : 10.7155/jgaa.00610. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00610/

Cité par Sources :