On Two-Directional Orthogonal Ray Graphs

• Item type: SIG Technical Reports(1)
• 公開日: 2009-11-20
• タイトル: On Two-Directional Orthogonal Ray Graphs
• タイトル / 言語: en
• タイトル: On Two-Directional Orthogonal Ray Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Communications and Integrated Systems, Tokyo Institute of Technology
• 著者所属: Department of Communications and Integrated Systems, Tokyo Institute of Technology
• 著者所属: Department of Communications and Integrated Systems, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Communications and Integrated Systems, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Communications and Integrated Systems, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Communications and Integrated Systems, Tokyo Institute of Technology
• 著者名: AnishManSinghShrestha; Satoshi, Tayu; Shuichi, Ueno
• 著者名(英): Anish, ManSinghShrestha; Satoshi, Tayu; Shuichi, Ueno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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 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 provides 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. Our results settle an open question on the recognition of certain forbidden submatrices.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 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 provides 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. Our results settle an open question on the recognition of certain forbidden submatrices.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009-AL-127, 号 6, p. 1-8, 発行日 2009-11-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会