Crossing Angles of Geometric Graphs

Authors

  • Karin Arikushi
  • Csaba Tóth

DOI:

https://doi.org/10.7155/jgaa.00329

Keywords:

geometric graph , crossing anlge , rigidity

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.

Downloads

Download data is not yet available.

Downloads

Published

2014-05-01

How to Cite

Arikushi, K., & Tóth, C. (2014). Crossing Angles of Geometric Graphs. Journal of Graph Algorithms and Applications, 18(3), 401–420. https://doi.org/10.7155/jgaa.00329

Issue

Section

Articles

Categories