Crossing Angles of Geometric Graphs
We study the crossing angles of geometric graphs in the plane. We introduce the crossing angle number of a graph G, denoted can(G), which is the minimum number of angles between crossing edges in a straight line drawing of G. We show that an n-vertex graph G with can(G) = O(1) has O(n) edges, but there are graphs G with bounded degree and arbitrarily large can(G). We also initiate studying the global crossing-angle rigidity of geometric graphs. We construct bounded degree graphs G = (V,E) such that for any two straight-line drawings of G with the same prescribed crossing angles, there is a subset V′ ⊂ V of |V′| ≥ |V|/2 vertices that are similar in the two drawings.