BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20251102T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69e36c9733b2a
DTSTART;TZID=America/Toronto:20260327T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20260327T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-therese-biedl-planar-graph-drawing-meet
SUMMARY:Tutte Colloquium -Therese Biedl-Planar graph drawing\, meet MSOL
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n Therese Biedl\n\nAFFILIATION:\n University of Waterl
 oo\n\nLOCATION:\n MC 5501\n\nABSTRACT: It is well-known that every planar
  graph has a planar\ndrawing with straight-line segments\, even if vertice
 s are restricted\nto lie on a grid with linear coordinates.  In this talk
 \, we will\nstudy the question of finding planar graph drawings where the 
 height H\nof the grid is as small as possible.   Dujmovic et al gave an\n
 FPT-algorithm that finds the minimum height.  However\, it is not\npartic
 ularly adaptable to closely related problems\, such as finding\nrectilinea
 r drawings of minimum height.    We therefore study a new\nand completel
 y different approach to test whether a graph has a\ndrawing of height H. 
     Since such graphs have pathwidth O(H)\, a\nnatural approach is to ap
 peal to Courcelle's theorem.  This requires\nphrasing the problem in so-c
 alled monadic second-order logic (MSOL)\,\nbut MSOL supports neither arbit
 rarily large integers nor permutations\,\nmaking it difficult to use for g
 raph drawing problems.   In this\ntalk\, we show that with some detours w
 e can phrase the question of\nwhether G has a straight-line drawing of hei
 ght H in a radically\ndifferent way (\"no face has a fish\") that can be e
 asily expressed in\nMSOL.\n\n(Joint work with Ignaz Rutter)
DTSTAMP:20260418T113551Z
END:VEVENT
END:VCALENDAR