Abstract: Graph invariants are properties of a graph that solely depend on the graph structure and remain unchanged regardless of the representation or labeling of the graph. My research focuses on twin-width, a recently discovered graph invariant that has quickly attracted substantial interest within the research community. Twin-width of a graph measures how the graph is to a “cograph.” Here, cographs are a special type of graph, whose twin-width is exactly zero, and many computationally difficult (Np-Hard) problems, e.g., max clique problem, can be solved efficiently on cographs. If a graph has a low twin-width, it is closer to being a cograph; hence, many hard problems can be solved efficiently. Unfortunately, computing the twin-width of a graph is itself an Np-Hard problem. Nonetheless, twin-width is bounded for many graph classes—including planar graphs, and its algorithmic applications are especially relevant for these classes. Finding the exact twin-width bound for planar graphs is a well-attempted problem, yet it remains open. We considered two important subclasses of planar graphs, namely the outerplanar graphs and the plane 3-trees. We proved that their twin-width bound is three and five, respectively. Towards proving these results, we discovered several new structural properties of these two graph classes which are of independent interest. Also, some of these structural results can be generalized for graph classes beyond planar graphs; however, using those to find their twin-width bounds is left as future work.

 

Presenter:  Muhammad Anwarul Azim (Student No. 0422052044)

Venue: Graduate Seminar Room