Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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 )

Ordered Level Planarity

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)

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login