Right angle crossing graphs and 1-planarity ?
A Right Angle Crossing Graph (also called a RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A 1 1 -planar graph is a graph that has a drawing where every edge is crossed at most once. This paper studies the combinatorial relationship between the family of RAC graphs and the family of 1 1 -planar graphs. It is proved that: (1)all RAC graphs having maximal edge density belong to the intersection of the two families; and (2)there is no inclusion relationship between the two families. As a by-product of the proof technique, it is also shown that every RAC graph with maximal edge density is the union of two maximal planar graphs.
1-planarity rac graphs geometric graph theory