Crossing Angles of Geometric Graphs
Karin Arikushi, Csaba D. Tóth · Journal of Graph Algorithms and Applications · 2014
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 the study of global crossing angle rigidity for geometric graphs. We construct bounded degree graphs G=(V,E) such that for any two straight-line drawings of G with the same crossing angle pattern, there is a subset V??? ??? V of |V???| ??? |V|/2 vertices that are embedded into similar point sets in the two drawings.