On two-directional orthogonal ray graphs

An orthogonal ray graph is an intersection graph of horizontal and vertical rays (half-lines) in the xy-plane. An orthogonal ray graph is a 2-directional orthogonal ray graph if all the horizontal rays extend in the positive a;-direction and all the vertical rays extend in the positive x-direction. We show several characterizations of 2-directional orthogonal ray graphs. We first show a forbidden submatrix characterization of 2-directional orthogonal ray graphs. A characterization in terms of a vertex ordering follows immediately. Next, we show that 2-directional orthogonal ray graphs are exactly those bipartite graphs whose complements are circular arc graphs. This characterization leads to polynomial-time recognition and isomorphism algorithms for 2-directional orthogonal ray graphs. Our results settle an open question on the recognition of certain forbidden submatrices.