Published by the Department of Computer Science, The University of Chicago.

Abstract

A geometric graph G is an a angle crossing (alpha AC) graph if every pair of crossing edges in G cross at an angle of at least alpha. The concept of right angle crossing (RAC) graphs alpha = pi/2) was recently introduced by Didimo et al. [10]. It was shown that any RAC graph with n 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 alphaAC graphs for all 0 < alpha < pi/2.

• The article: PDF (305,741 bytes)
• Source material: ZIP (225,704 bytes)
• Self citation in BIBTeX (313 bytes)

© 2011 Vida Dujmovic, Joachim Gudmundsson, Pat Morin and Thomas Wolle
Licensed under a Creative Commons Attribution License

2011, Article 5

2011 Article 3

Special Issue

Published articles