LORENZO BALZOTTI

PhD Graduate

PhD program:: XXXV


supervisor: 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/1702607 - 2024 - How vulnerable is an undirected planar graph with respect to max flow
Balzotti, Lorenzo; Franciosa, Paolo G. - 01a Articolo in rivista
paper: 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. 570-586 - issn: 0028-3045 - wos: WOS:001135840500001 (0) - scopus: 2-s2.0-85181244509 (1)

11573/1703578 - 2024 - Non-crossing shortest paths lengths in planar graphs in linear time
Balzotti, Lorenzo; Franciosa, Paolo G. - 01a Articolo in rivista
paper: 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/1711344 - 2024 - INTEND: Intent-Based Data Operation in the Computing Continuum
Firmani, Donatella; Leotta, Francesco; Mathew, Jerin George; Rossi, Jacopo; Balzotti, Lorenzo; Song, Hui; Roman, Dumitru; Dautov, Rustem; Johannes Husom, Erik; Sen, Sagar; Balionyte-Merle, Vilija; Morichetta, Andrea; Dustdar, Schahram; Metsch, Thijs; Frascolla, Valerio; Khalid, Ahmed; Landi, Giada; Brenes, Juan; Toma, Ioan; Szabó, Róbert; Schaefer, Christian; Udroiu, Cosmin; Ulisses, Alexandre; Pietsch, Verena; Akselsen, Sigmund; Munch-Ellingsen, Arne; Pavlova, Irena; Kim, Hong-Gee; Kim, Changsoo; Allen, Bob; Kim, Sunwoo; Paulson, Eberechukwu - 04b Atto di convegno in volume
conference: International Conference on Advanced Information Systems Engineering (Limassol; Cyprus)
book: Proceedings of the Research Projects Exhibition Papers Presented at the 36th International Conference on Advanced Information Systems Engineering (CAiSE 2024) - ()

11573/1686470 - 2023 - Two new characterizations of path graphs
Apollonio, Nicola; Balzotti, Lorenzo - 01a Articolo in rivista
paper: 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. 1-15 - 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
conference: 13th International Conference, CIAC 2023 (Larnaca; Cyprus)
book: 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
conference: 13th International Conference, CIAC 2023 (Larnaca; Cyprus)
book: 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
conference: Computer science - theory and applications - 17th international computer science symposium in Russia, {CSR} 2022 (Russia)
book: 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
paper: 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: 2-s2.0-85146367052 (5)

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