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 3*n*-6
edges does not have a planar drawing.

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 (π/α)(3*n*-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=72^{o},
has at most 6*n*-o(n) edges.