Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00329
Crossing Angles of Geometric Graphs
Karin Arikushi and
Csaba D. Tóth
Vol. 18, no. 3, pp. 401420, 2014. Regular paper.
Abstract 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 straightline drawing of G. We show that an nvertex 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 straightline 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.

Submitted: February 2014.
Reviewed: April 2014.
Revised: May 2014.
Accepted: June 2014.
Final: July 2014.
Published: July 2014.
Communicated by
Giuseppe Liotta

Journal Supporters
