On orthogonal ray trees
| Autor: | Asahi Takaoka, Irina Mustaţa, Shuichi Ueno, Satoshi Tayu, Kousuke Nishikawa |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Block graph Astrophysics::High Energy Astrophysical Phenomena Applied Mathematics 0102 computer and information sciences 02 engineering and technology Intersection graph 01 natural sciences 1-planar graph Tree (graph theory) law.invention Planar graph Combinatorics symbols.namesake 010201 computation theory & mathematics law Outerplanar graph Line graph 0202 electrical engineering electronic engineering information engineering symbols Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Theta graph Mathematics |
| Zdroj: | Discrete Applied Mathematics. 201:201-212 |
| ISSN: | 0166-218X |
| Popis: | An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane, which is introduced in connection with the defect-tolerant design of nano-circuits. An orthogonal ray graph is a 3-directional orthogonal ray graph if every vertical ray has the same direction. A 3-directional orthogonal ray graph is a 2-directional orthogonal ray graph if every horizontal ray has the same direction. The characterizations and the complexity of the recognition problem have been open for orthogonal ray graphs and 3-directional orthogonal ray graphs, while various characterizations with a quadratic-time recognition algorithm have been known for 2-directional orthogonal ray graphs. In this paper, we show several characterizations with a linear-time recognition algorithm for orthogonal ray trees by using the 2-directional orthogonal ray trees. We also show that a tree is a 3-directional orthogonal ray graph if and only if it is a 2-directional orthogonal ray graph. Moreover, we show some necessary conditions for orthogonal ray graphs and 3-directional orthogonal ray graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect