On RAC Drawings of Graphs with one Bend per Edge
When
Tuesday, Sept 11th at 5:00 PM
Where
Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor
Speaker
Henry Förster
PhD Student in Computer Science
University of Tübingen
Abstract
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
