On 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 x-direction and all the vertical rays extend in the positive y-direction. We first show that the class of orthogonal ray graphs is a proper subset of the class of unit grid intersection graphs. We next provide several characterizations of 2-directional orthogonal ray graphs. Our first characterization is based on forbidden submatrices. 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 implies polynomial-time recognition and isomorphism algorithms for 2-directional orthogonal ray graphs. It also leads to a characterization of 2-directional orthogonal ray graphs by a list of forbidden induced subgraphs. We also show a characterization of 2-directional orthogonal ray trees, which implies a linear-time algorithm to recognize such trees. Our results settle an open question of deciding whether a (0. 1)-matrix can be permuted to avoid the submatrices (C) 2010 Elsevier B.V. All rights reserved.