BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260917T113329Z
UID:Seminar-dept-1029@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230321T130000
DTEND:20230321T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Siddharth Gupta: Drawing Graphs on the Grid: How Easy Is It?\n\nGrid 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1029
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR