BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:abc336b1-e8cc-42e3-be88-c3e80b1e02bb
X-WR-CALNAME:[gt.go] - 'Outerplanar directed acyclic graphs have constant s
 tack number' by Laura Merker
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20241027T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20220327T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20230326T020000
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:abc336b1-e8cc-42e3-be88-c3e80b1e02bb
DTSTAMP:20260408T112046Z
CLASS:PUBLIC
DESCRIPTION:/Exposé en anglais/Talk in english/ \n\nThe stack number of a d
 irected acyclic graph G is the minimum k for which there is a topological 
 ordering of G and a k-coloring of the edges such that no two edges of the 
 same color cross\, i.e.\, have alternating endpoints along the topological
  ordering. We prove that the stack number of directed acyclic outerplanar 
 graphs is bounded by a constant\, which gives a positive answer to a conje
 cture by Heath\, Pemmaraju and Trenk [SIAM J. Computing\, 1999]. As an imm
 ediate consequence\, this shows that all upward outerplanar graphs have co
 nstant stack number\, answering a question by Bhore et al. [GD 2021] and t
 hereby making significant progress towards the problem for general upward 
 planar graphs originating from Nowakowski and Parker [Order\, 1989]. As ou
 r main tool we develop the novel technique of directed H-partitions\, whic
 h might be of independent interest. \n\nWe complement the bounded stack nu
 mber for directed acyclic outerplanar graphs by constructing a family of d
 irected acyclic 2-trees that have unbounded stack number\, thereby refutin
 g a conjecture by Nöllenburg and Pupyrev [arXiv:2107.13658\, 2021]. \n\nIn
  this talk we introduce the concepts of stack layouts and directed H-parti
 tions and sketch some of the techniques and proofs. \n\nJoint work with Pa
 ul Jungeblut and Torsten Ueckerdt. \n\n[Laura Merker] (Karlsruhe Institute
  of Technology\, Institute of theoretical Informatics ) \n\nhttps://i11www
 .iti.kit.edu/en/members/laura_merker/index \n\n\n\nRemarks / Remarques \n
 \nFind all the information of the working group on this [ https://graphese
 toptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] . \nR
 etrouvez toutes les informations du GT sur cette [ https://graphesetoptimi
 sation.labri.fr/pmwiki.php/Groupe/GT | page web ] .
DTSTART;TZID=Europe/Paris:20230324T140000
DTEND;TZID=Europe/Paris:20230324T150000
LOCATION:https://webconf.u-bordeaux.fr/b/mar-ef4-zed and LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'Outerplanar directed acyclic graphs have constant stack 
 number' by Laura Merker
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
