Lorenzo Balzotti, Donatella Firmani, Jerin George Mathew, Riccardo Torlone, Sihem Amer-Yahia. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Given a plane graph it is known how to compute the union of non-crossing shortest paths. These algorithms do not allow neither to list each single shortest path nor to compute length of shortest paths. Given the union of non-crossing shortest paths, we introduce the concept of shortcuts that allows us to establish whether a path is a shortest path by checking local properties on faces of the graph. By using shortcuts we can compute the length of each shortest path, given their union, in total linear time, and we can list each shortest path p in O(max{ℓ,ℓloglogkℓ}), where ℓ is the number of edges in p and k the number of shortest paths.

Abstract We study the problem of computing the vitality of edges and vertices with respect to the ‐max flow in undirected planar graphs, where the vitality of an edge/vertex is the ‐max flow decrease when the edge/vertex is removed from the graph. This allows us to establish the vulnerability of the graph with respect to the ‐max flow. We give efficient algorithms to compute an additive guaranteed approximation of the vitality of edges and vertices in planar undirected graphs. We show that in the general case high vitality values are well approximated in time close to the time currently required to compute ‐max flow . We also give improved, and sometimes optimal, results in the case of integer capacities. All our algorithms work in space.