Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 18, 2021, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Meghana M. Reddy
A simple drawing of a graph is a topological drawing where any two edges have at most one point in common, including common endpoints. It has been shown that k-planar graphs, where k = 0,1,2,3 also admit k-plane simple drawings. However, there exist 4-planar graphs which do not admit a 4-plane simple drawing, and the idea can be extended to k-planar graphs for k > 4. In a Mittagsseminar talk in April 2020, we proved that there exists a function f : N -> N such that every k-planar graph admits an f(k)-plane simple drawing for all k > 3. This answered a question posed by Schaefer. In this talk, we prove an improved bound for 4-planar graphs and show that every 4-planar graph admits an 8-plane simple drawing. In contrast, we prove that when restricted to straight-line drawings instead of simple drawings, there exist 1-planar graphs which require unbounded number of crossings per edge. This is joint work with Chih-Hung Liu, Michael Hoffmann and Csaba D. Tóth.
Automatic MiSe System Software Version 1.4803M | admin login