On the Recognition of Four-Directional Orthogonal Ray Graphs

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.