A Survey on Graph Drawing Beyond Planarity <s> Density of straight-line RAC graphs, ACEα graphs, and ACLα graphs. <s> A graph G is an a-angle crossing (aAC) graph if every pair of crossing edges in G intersect at an angle of at least a. The concept of right angle crossing (RAC) graphs (a=Pi/2) was recently introduced by Didimo et. al. 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 aAC graphs for all 0 < a < Pi/2. <s> BIB001 </s> A Survey on Graph Drawing Beyond Planarity <s> Density of straight-line RAC graphs, ACEα graphs, and ACLα graphs. <s> We consider graphs that admit polyline drawings where all crossings occur at the same angle α ∈ (0, π/2). We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has O(n) edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest. <s> BIB002
Since straight-line RAC graphs are fan-crossing-free, they cannot have more than 4n − 9 edges. In fact, the maximum number of edges of a straight-line RAC graph is 4n − 10  , and for each k ≥ 3 there exists a straight-line RAC graph G k with n = 3k − 5 vertices and 4n − 10 edges (i.e., optimal). Graph G k is constructed as follows (see Figure 4 (d)): (i) start from a triangulated plane graph on k vertices; (ii) add to this graph its dual, except for the node corresponding to the external face; (iii) for each node u of the dual, add the three edges that connect u to the three vertices of the face corresponding to u. The fact that two edges of a straight-line RAC drawing Γ of a graph G can cross only at right angles immediately implies that the crossing graph of Γ is bipartite; the crossing graph of Γ has a vertex v e for each edge e of G and an edge (v e , v e ) if the e and e cross in Γ. Hence, we can bi-color the edges of G such that each color set induces a planar graph, which implies that G has at most 6n − 12 edges. The 4n − 10 bound is proved by exploiting a finer coloring of the edges of G with three colors and different counting arguments based on Euler's formula for planar graphs  . Dujmovic et al. provide an alternative proof of this bound, based on charging techniques BIB001 . They also show that straight-line ACLα graphs have at most π α (3n − 6) edges; the proof is based on a partition of the edges into distinct buckets, according to their directions, so that each bucket induces a planar graph. With similar arguments, it is shown that straight-line ACEα graphs have at most 3(3n − 6) edges BIB002 . These bounds for ACLα and ACEα graphs are not known to be tight.