LORENZO BALZOTTI

Dottore di ricerca

ciclo: XXXV


supervisore: Alessandro Savo
relatore: Paolo Giulio Franciosa

Titolo della tesi: 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.

Produzione scientifica

11573/1702607 - 2024 - How vulnerable is an undirected planar graph with respect to max flow
Balzotti, Lorenzo; Franciosa, Paolo G. - 01a Articolo in rivista
rivista: NETWORKS (John Wiley & Sons Incorporated:Customer Service, 111 River Street:Hoboken, NJ 07030:(800)225-5945, (201)748-6000, EMAIL: societyinfo@wiley.com, INTERNET: http://www.wiley.com, Fax: (212)748-6551) pp. 1-17 - issn: 0028-3045 - wos: WOS:001135840500001 (0) - scopus: 2-s2.0-85181244509 (0)

11573/1703578 - 2024 - Non-crossing shortest paths lengths in planar graphs in linear time
Balzotti, Lorenzo; Franciosa, Paolo G. - 01a Articolo in rivista
rivista: DISCRETE APPLIED MATHEMATICS (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598) pp. 183-191 - issn: 0166-218X - wos: WOS:001145058700001 (1) - scopus: 2-s2.0-85180968575 (1)

11573/1686470 - 2023 - Two new characterizations of path graphs
Apollonio, Nicola; Balzotti, Lorenzo - 01a Articolo in rivista
rivista: DISCRETE MATHEMATICS (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598) pp. 113596- - issn: 0012-365X - wos: WOS:001048436500001 (0) - scopus: 2-s2.0-85165585153 (0)

11573/1678848 - 2023 - Non-crossing Shortest Paths Lengths in Planar Graphs in Linear Time
Balzotti, Lorenzo; Franciosa, Paolo G. - 04b Atto di convegno in volume
congresso: 13th International Conference, CIAC 2023 (Larnaca; Cyprus)
libro: Algorithms and Complexity. CIAC 2023. Lecture Notes in Computer Science, vol 13898. Springer - (978-3-031-30447-7; 978-3-031-30448-4)

11573/1678849 - 2023 - How Vulnerable is an Undirected Planar Graph with Respect to Max Flow
Balzotti, Lorenzo; Franciosa, Paolo G. - 04b Atto di convegno in volume
congresso: 13th International Conference, CIAC 2023 (Larnaca; Cyprus)
libro: Algorithms and Complexity. CIAC 2023. Lecture Notes in Computer Science, vol 13898. Springer - (978-3-031-30447-7; 978-3-031-30448-4)

11573/1665275 - 2022 - Non-crossing shortest paths in undirected unweighted planar graphs in linear time
Balzotti, Lorenzo; Franciosa, Paolo G. - 04b Atto di convegno in volume
congresso: Computer science - theory and applications - 17th international computer science symposium in Russia, {CSR} 2022 (Russia)
libro: Computer science - theory and applications - 17th international computer science symposium in Russia, {CSR} 2022, virtual event, June 29 - July 1, 2022, Proceedings - (978-3-031-09573-3; 978-3-031-09574-0)

11573/1665278 - 2022 - Non-crossing shortest paths in undirected unweighted planar graphs in linear time
Balzotti, Lorenzo; Franciosa, Paolo G. - 01a Articolo in rivista
rivista: JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS (Department of Computer Science / Brown University:115 Waterman Street:Providence, RI 02912:(401)863-7639, EMAIL: rt@cs.brown.edu, tollis@utdallas.edu, INTERNET: http://www.cs.brown.edu/publications/jgaa, Fax: (401)863-7657) pp. 589-606 - issn: 1526-1719 - wos: (0) - scopus: (0)

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