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. 401-420, 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 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.
Submitted: February 2014.
Reviewed: April 2014.
Revised: May 2014.
Accepted: June 2014.
Final: July 2014.
Published: July 2014.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX