Seminar Announcement
Date: Thursday, 21 September 2023
Time: 3:30 - 4:30 PM
Venue: Lecture hall 06
Product Structure of Planar Graphs
Harish Chandramouleeswaran
Chennai Mathematical Institute.
21-09-23

---

Abstract

We describe an algorithm due to Dujmović et al. to write any (finite, simple, and undirected) planar graph as a strong graph product of a graph of bounded treewidth and a path. This technique has led to the resolution of several longstanding open problems in graph theory, via solving those problems for graphs of bounded treewidth and then "lifting" the solution to general planar graphs by using the said decomposition. We will start by defining all the necessary terms, give an overview of the flurry of recent work in graph product structure theory, and state a couple of graph-theoretic applications. The focus of the talk will be the description of an O(n^2)-time decomposition algorithm due to Dujmović et al. (FOCS 2019, J. ACM 2020) for n-vertex planar graphs.