Felsner, S. and Mertzios, G.B. and Mustata, I. (2013) 'On the recognition of four-directional orthogonal ray graphs.', in *Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings.* Berlin, Heidelberg: Springer, pp. 373-384. Lecture notes in computer science. (8087).

## Abstract

Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4-directional orthogonal ray graph (4-DORG). Otherwise, if all rays are only pointing into the positive x and y directions, the intersection graph is a 2-DORG. Similarly, for 3-DORGs, the horizontal rays can have any direction but the vertical ones can only have the positive direction. The recognition problem of 2-DORGs, which are a nice subclass of bipartite comparability graphs, is known to be polynomial, while the recognition problems for 3-DORGs and 4-DORGs are open. Recently it has been shown that the recognition of unit grid intersection graphs, a superclass of 4-DORGs, is NP-complete. In this paper we prove that the recognition problem of 4-DORGs is polynomial, given a partition {L,R,U,D} of the vertices of G (which corresponds to the four possible ray directions). For the proof, given the graph G, we first construct two cliques G 1,G 2 with both directed and undirected edges. Then we successively augment these two graphs, constructing eventually a graph TeX with both directed and undirected edges, such that G has a 4-DORG representation if and only if TeX has a transitive orientation respecting its directed edges. As a crucial tool for our analysis we introduce the notion of an S-orientation of a graph, which extends the notion of a transitive orientation. We expect that our proof ideas will be useful also in other situations. Using an independent approach we show that, given a permutation π of the vertices of U (π is the order of y-coordinates of ray endpoints for U), while the partition {L,R} of V ∖ U is not given, we can still efficiently check whether G has a 3-DORG representation.

Item Type: | Book chapter |
---|---|

Full text: | (AM) Accepted Manuscript Download PDF (390Kb) |

Status: | Peer-reviewed |

Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-40313-2_34 |

Publisher statement: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-40313-2_34 |

Date accepted: | No date available |

Date deposited: | 17 September 2014 |

Date of first online publication: | 2013 |

Date first made open access: | No date available |

## Save or Share this output

Export: | |

Look up in GoogleScholar |