## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

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

 Mittagsseminar Talk Information

Date and Time: Tuesday, February 22, 2022, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Meghana M. Reddy

## Simplifying Non-simple Fan-Planar Drawings

A drawing of a graph is fan-planar if the edges intersecting a common edge $a$ share a vertex $A$ on the same side of $a$. More precisely, orienting $e$ arbitrarily and the other edges towards $A$ results in a consistent orientation of the crossings. So far, fan-planar drawings have only been considered in the context of simple drawings, where any two edges share at most one point, including endpoints. We show that every non-simple fan-planar drawing can be redrawn as a simple fan-planar drawing of the same graph while not introducing additional crossings, thereby answering an open problem posed by Kaufmann and Ueckerdt in 2014. Combined with previous results on fan-planar drawings, this yields that $n$-vertex-graphs having such a drawing can have at most $6.5n$ edges and that the recognition of such graphs is NP-hard. This is joint work with Boris Klemz, Kristin Knorr and Felix Schröder.

Information for students and suggested topics for student talks