Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings
复制标题
计算机科学数学基础 2013 - 第 38 届国际研讨会，MFCS 2013，奥地利克洛斯特新堡，2013 年 8 月 26-30 日。
DOI：
10.1007/978-3-642-40313-2_34
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Felsner S
中科院分区：
文献类型：
--
作者：
Felsner S
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 positivexandydirections, the intersection graph is a2-DORG. Similarly, for3-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 ofG(which corresponds to the four possible ray directions). For the proof, given the graphG, we first construct two cliquesG1,G2with both directed and undirected edges. Then we successively augment these two graphs, constructing eventually a graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\widetilde{G}$\end{document} with both directed and undirected edges, such thatGhas a 4-DORG representation if and only if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\widetilde{G}$\end{document} has a transitive orientation respecting its directed edges. As a crucial tool for our analysis we introduce the notion of anS-orientationof 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 ofU(πis the order ofy-coordinates of ray endpoints forU), while the partition {L,R} ofV∖Uis not given, we can still efficiently check whetherGhas a 3-DORG representation.
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 positivexandydirections, the intersection graph is a2-DORG. Similarly, for3-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 ofG(which corresponds to the four possible ray directions). For the proof, given the graphG, we first construct two cliquesG1,G2with both directed and undirected edges. Then we successively augment these two graphs, constructing eventually a graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\widetilde{G}$\end{document} with both directed and undirected edges, such thatGhas a 4-DORG representation if and only if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\widetilde{G}$\end{document} has a transitive orientation respecting its directed edges. As a crucial tool for our analysis we introduce the notion of anS-orientationof 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 ofU(πis the order ofy-coordinates of ray endpoints forU), while the partition {L,R} ofV∖Uis not given, we can still efficiently check whetherGhas a 3-DORG representation.