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

Date and Time: Tuesday, February 23, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Alexander Pilz

Deciding Monotonicity of Good Drawings of the Complete Graph

In the presented work, we investigate x-monotone drawings of complete graphs. We are interested in good drawings of the complete graph K_n. In a good drawing of a graph no two edges share more than one point (either a common end vertex or a crossing) and no edge crosses itself. Thus, good drawings are a generalization of geometric graphs. An important motivation to focus the attention on good drawings is that every crossing-minimal drawing of a graph is good. We describe an O(n⁵) time algorithm for deciding whether a good drawing of the complete graph K_n, given in terms of its rotation system, can be re-drawn using only x-monotone arcs. (Joint work with O. Aichholzer, T. Hackl, G. Salazar, and B. Vogtenhuber.)

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