Circular right-angle crossing drawings in linear time

A common representational style for drawing graphs is the so-called circular drawings, where vertices are represented as points on a circle, and edges are represented as straight line segments. In such drawings, edges may cross; these edge crossings have a negative effect on human readability.Recent empirical research shows that increasing the angles of edge crossings reduces the negative effect of crossings on human readability. This result has motivated a number of recent investigations of right angle crossing   graph drawings, where each crossing angle is π2.The main result of this paper is a characterization of graphs that admit a circular right angle crossing drawing. We present a linear-time algorithm for testing and constructing such a drawing of a graph, if it exists.Further, we give an upper bound on the number of edges in a circular right angle crossing drawing, and we note that the optimization problem of constructing circular drawings with large angle crossings can be formulated as a quadratic programming problem.