|
Public viva-voce Notification Date: 22 April 2025 Time: 02.30 PM Venue: Seminar Hall (Hybrid) Some problems on planar and minor free graphs Archit Chauhan Chennai Mathematical Institute. 22-04-25 Abstract We look at two well known problems in graph theory in this work. The first part of this work deals with the parallel complexity of Depth First Search. Depth First Search in graphs is a famous algorithm for traversing graphs, which has played a pivotal role in the study of several other problems such as biconnectivity, triconnectivity, topological sorting, strong connectivity, planarity testing and embedding etc. While a simple polynomial time algorithm exists for constructing a DFS tree, the existence of a deterministic efficient parallel algorithm remains an open problem. In restricted graph classes like planar graphs however, deterministic parallel algorithms for DFS have been found (for directed as well as undirected graphs), one of them being Hagerup's elegant algorithm for DFS in undirected planar graphs via decomposition into lateral layers. We propose a generalisation of Hagerup's decomposition for directed planar graphs and use it to give an efficient parallel algorithm for DFS in such graphs. We also give efficient parallel algorithms for DFS in bounded treewidth graphs, bounded genus graphs, and single-crossing-minor-free graphs, where the latter two classes are generalizations of planar graphs. Continuing with the thread of extending efficient algorithms for planar graphs to more general graph classes, we look at the problem of finding a simple path of even length between two given vertices of a graph, which we call the Even Path problem. While the problem is tractable in undirected graphs, it is known to be NP-complete in general directed graphs. In planar directed graphs, Nedev showed that a polynomial time algorithm for the problem exists. We extend the class of graphs for which the Even Path problem is known to be tractable, by giving a polynomial-time algorithm for it in directed single-crossing-minor-free graphs. We also give solutions to two other related problems that occur along the way, that might be of independent interest. All are invited to attend the viva-voce examination.
|
