Notes on Large Angle Crossing Graphs

Dujmovic, V., Gudmundsson, J., Morin, P. and Wolle, T.

A graph α is an α angle crossing (αAC) graph if every pair of crossing edges in α intersect at an angle of at least α. The concept of right angle crossing (RAC) graphs (α = π/2) was recently introduced by Didimo et al. [7]. It was shown that any RAC graph with α vertices has at most 4n − 10 edges and that there are infinitely many values of n for which there exists a RAC graph with n vertices and 4n − 10 edges. In this paper, we give upper and lower bounds for the number of edges in αAC graphs for all 0 < α < π/2.

Cite as: Dujmovic, V., Gudmundsson, J., Morin, P. and Wolle, T. (2010). Notes on Large Angle Crossing Graphs. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 19-24

(from crpit.com) (local if available)