Drawing Graphs on the Grid: How Easy Is It?

21^st March 2023, 13:00 Ashton Lecture Theatre
Dr. Siddharth Gupta
Department of Computer Science, University of Warwick

Abstract

Grid graphs, and, more generally, $k \times r$ grid graphs, form one of the most basic classes of geometric graphs. Over the past few decades, a large body of work has studied the (in)tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is particularly hard -- it was shown to be NP-hard even on trees of pathwidth 3 already in 1987. In this talk, I will talk about some positive and negative results in this regard in the framework of parameterized complexity. I will also briefly talk about the area of Graph Drawing and Parameterized Complexity whose intersection this problem lies in.