LORENZO BALZOTTI

PhD Graduate

PhD program:: XXXV


tutor: Alessandro Savo
advisor: Paolo Giulio Franciosa

Thesis title: Non-Crossing Shortest Paths in Planar Graphs with Applications to Max Flow, and Path Graphs

This thesis is concerned with non-crossing shortest paths in planar graphs with applications to st-max flow vitality and path graphs. In the first part we deal with non-crossing shortest paths in a plane graph G, i.e., a planar graph with a fixed planar embedding, whose extremal vertices lie on the same face of G. The first two results are the computation of the lengths of the non-crossing shortest paths knowing their union, and the computation of the union in the unweighted case. Both results require linear time and we use them to describe an efficient algorithm able to give an additive guaranteed approximation of edge and vertex vitalities with respect to the st-max flow in undirected planar graphs, that is the max flow decrease when the edge/vertex is removed from the graph. Indeed, it is well-known that the st-max flow in an undirected planar graph can be reduced to a problem of non-crossing shortest paths in the dual graph. We conclude this part by showing that the union of non-crossing shortest paths in a plane graph can be covered with four forests so that each path is contained in at least one forest. In the second part of the thesis we deal with path graphs and directed path graphs, where a (directed) path graph is the intersection graph of paths in a (directed) tree. We introduce a new characterization of path graphs that simplifies the existing ones in the literature. This characterization leads to a new list of local forbidden subgraphs of path graphs and to a new algorithm able to recognize path graphs and directed path graphs. This algorithm is more intuitive than the existing ones and does not require sophisticated data structures.

Research products

  • 11573/1501676 - 2020 - Computing Lengths of Shortest Non-Crossing Paths in Planar Graphs (13c Pubblicazione su portale)
    BALZOTTI, LORENZO; FRANCIOSA, PAOLO GIULIO
  • 11573/1627343 - 2021 - Multi-Terminal Shortest Paths in Unit-Weight Planar Graphs in Linear Time (13c Pubblicazione su portale)
    BALZOTTI, LORENZO; FRANCIOSA, PAOLO GIULIO
  • 11573/1638674 - 2021 - A New Characterization of Path Graphs (13c Pubblicazione su portale)
    BALZOTTI, LORENZO
  • 11573/1638677 - 2021 - A New Algorithm to Recognize Path Graphs and Directed Path Graphs (13c Pubblicazione su portale)
    BALZOTTI, LORENZO
  • 11573/1638680 - 2022 - Max Flow Vitality of Edges and Vertices in Undirected Planar Graphs (13c Pubblicazione su portale)
    BALZOTTI, LORENZO; FRANCIOSA, PAOLO GIULIO
  • 11573/1638683 - 2022 - A Linear Time Algorithm for Computing Max-Flow Vitality in Undirected Unweighted Planar Graphs (13c Pubblicazione su portale)
    AUSIELLO, GIORGIO; BALZOTTI, LORENZO; FRANCIOSA, PAOLO GIULIO; LARI, ISABELLA; RIBICHINI, ANDREA
  • 11573/1665278 - 2022 - Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time (01a Articolo in rivista)
    BALZOTTI, LORENZO; FRANCIOSA, PAOLO GIULIO
  • 11573/1665275 - 2022 - Non-crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time (04b Atto di convegno in volume)
    BALZOTTI, LORENZO; FRANCIOSA, PAOLO GIULIO

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma