Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 28, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Boris Klemz (Freie Universität Berlin )
We introduce and study the problem Ordered Level Planarity which asks for a planar drawing of a graph such that vertices are placed at prescribed positions in the plane and such that every edge is realized as a y-monotone curve. This can be interpreted as a variant of Level Planarity in which the vertices on each level appear in a prescribed total order.
Our main result is a NP-hardness statement for a very constrained special case, which allows us to provide simple reductions to several other graph embedding problems. We thereby solve open problems posed by Angelini, Da Lozzo, Di Battista, Frati, and Roselli, by Fulek, Pelsmajer, Schaefer, and Stefankovivc, and by Katz, Krug, Rutter, and Wolff.
(joint work with Günter Rote)
Automatic MiSe System Software Version 1.4803M | admin login