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 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.
- 一般社団法人情報処理学会の論文
- 2009-11-20
著者
-
Satoshi Tayu
Department Of Communications And Integrated Systems Tokyo Institute Of Technology
-
Shuichi Ueno
Department of Communications and Integrated Systems, Tokyo Institute of Technology
-
Shuichi Ueno
Department Of Communications And Integrated Systems Tokyo Institute Of Technology
-
Shuichi Ueno
Department of Communication and Computer Engineering, Tokyo Institute of Technology
関連論文
- On Two-Directional Orthogonal Ray Graphs
- Representation of Bipartite Graphs by OBDDs
- A Note on Two-Directional Orthogonal Ray Graphs and Related Graphs
- [招待講演]Orthogonal Ray Graphs with Applications to Nanocircuit Design
- Stable Matchings in Trees