On the Recognition of Four-Directional Orthogonal Ray Graphs

Felsner, S.; Mertzios, G.B.; Mustata, I.

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.

Citation

Felsner, S., Mertzios, G., & Mustata, I. (2013). On the Recognition of Four-Directional Orthogonal Ray Graphs. In K. Chatterjee, & J. Sgall (Eds.), Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings (373-384). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_34

• Publication Date: 2013
• Deposit Date: Sep 5, 2014
• Publicly Available Date: Sep 17, 2014
• Publisher: Springer Verlag
• Pages: 373-384
• Series Title: Lecture notes in computer science
• Book Title: Mathematical foundations of computer science 2013 : 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings.
• ISBN: 9783642403125
• DOI: https://doi.org/10.1007/978-3-642-40313-2_34
• Public URL: https://durham-repository.worktribe.com/output/1648288