Back to Search
Start Over
On orthogonal ray trees.
- Source :
-
Discrete Applied Mathematics . Mar2016, Vol. 201, p201-212. 12p. - Publication Year :
- 2016
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ORTHOGONALIZATION
*GRAPH theory
*ALGORITHMS
*SET theory
*MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 201
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 112674367
- Full Text :
- https://doi.org/10.1016/j.dam.2015.07.034