Pat Morin
The gold standard in graph drawing is the planar straight-line drawing; this is a drawing of a graph in the plane using line segments to represent edges so that no two edges in the drawing cross each other. Planar drawings are preferred because they are visually appealing and easy to read. However, not all graphs have planar drawings; Euler's formula implies that any graph with n vertices and more than 3n-6 edges does not have a planar drawing.
In a recent study using eye tracking hardware, Huang, Hong, and Eades showed that, contrary to popular belief, crossings have very little effect on the readability of a graph provided that edges that cross do not form any small angles. This motivates the study of α-angle crossing drawings in which edges that do cross each other must form a minimum angle of at least αIn this talk, we study the relationship between the minimum crossing angle, α, and the maximum number of edges of the graph. In particular, we give an upper-bound of (π/α)(3n-6) on the number of edges in such a graph. We also give a family of lower-bound constructions that shows our upper-bound is essentially optimal for any α of the form α=π/t-ε where t≥2 is an integer and ε>0 is an arbitrarily small constant. If sufficient time is available, we will also show that any drawing with minimum crossing angle α=2π/5=72o, has at most 6n-o(n) edges.
This talk is about joint work with Vida Dujmovic, Joachim Gudmundsson, and Thomas Wolle.