Tutte Colloquium -Therese Biedl-Planar graph drawing, meet MSOL

Abstract: It is well-known that every planar graph has a planar drawing with straight-line segments, even if vertices are restricted to lie on a grid with linear coordinates.  In this talk, we will study the question of finding planar graph drawings where the height H of the grid is as small as possible.   Dujmovic et al gave an FPT-algorithm that finds the minimum height.  However, it is not particularly adaptable to closely related problems, such as finding rectilinear drawings of minimum height.    We therefore study a new and completely different approach to test whether a graph has a drawing of height H.     Since such graphs have pathwidth O(H), a natural approach is to appeal to Courcelle's theorem.  This requires phrasing the problem in so-called monadic second-order logic (MSOL), but MSOL supports neither arbitrarily large integers nor permutations, making it difficult to use for graph drawing problems.   In this talk, we show that with some detours we can phrase the question of whether G has a straight-line drawing of height H in a radically different way ("no face has a fish") that can be easily expressed in MSOL.