کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421278 | 684176 | 2010 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On orthogonal ray graphs On orthogonal ray graphs](/preview/png/421278.png)
An orthogonal ray graph is an intersection graph of horizontal and vertical rays (half-lines) in the xyxy-plane. An orthogonal ray graph is a 2-directional orthogonal ray graph if all the horizontal rays extend in the positive xx-direction and all the vertical rays extend in the positive yy-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)(0,1)-matrix can be permuted to avoid the submatrices [1001]and[1011].
Journal: Discrete Applied Mathematics - Volume 158, Issue 15, 6 August 2010, Pages 1650–1659