Tuesday, Sept 11th at 5:00 PM
Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor
Henry Förster
PhD Student in Computer Science
University of Tübingen
A k-bend right-angle-crossing drawing or (k-bend RAC drawing}, for short) of a graph is a polyline drawing where each edge has at most k bends and the angles formed at the crossing points of the edges are 90 degrees. Accordingly, a graph that admits a k-bend RAC drawing is referred to as k-bend right-angle-crossing graph (or k-bend RAC, for short).
In this paper, we continue the study of the maximum edge-density of 1-bend RAC graphs. We show that an n-vertex 1-bend RAC graph cannot have more than 5.5n-11 edges. We also demonstrate that there exist infinitely many n-vertex 1-bend RAC graphs with exactly 5n-10 edges. Our results improve both the previously known best upper bound of 6.5n-O(1) edges and the corresponding lower bound of 4.5n-O(sqrt(n)) edges by Arikushi et al. (Comput. Geom. 45(4), 169–177 (2012)).
Joint work with Patrizio Angelini, Michael A. Bekos, and Michael Kaufmann