Intersection dimension of bipartite graphs
スポンサーリンク
概要
- 論文の詳細を見る
We introduce a concept of intersection dimension of a graph with respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes defined as intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graph-theoretic results, we show that the recognition problems for certain graph classes belong to NP.
- 2014-06-06
著者
-
Toshiki Saitoh
Japan Advanced Institute Of Science And Technology
-
Ryuhei Uehara
School Of Information Science Jaist
-
Yota Otachi
School of Information Science, Japan Advanced Institute of Science and Technology
-
Steven Chaplick
Institut fur Mathematik, Technische Universitat Berlin
-
Pavol Hell
School of Computing Science, Simon Fraser University
-
Toshiki Saitoh
Graduate School of Engineering, Kobe University
関連論文
- Efficient Enumeration of All Pseudoline Arrangements
- Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
- Approximating the path-distance-width for k-cocomparability graphs
- Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
- NP-completeness of generalized Kaboozle
- Computational Complexity of Piano-Hinged Dissections
- Bumpy Pyramid Folding Problem
- Zipper Unfolding of Domes and Prismoids
- Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
- Intersection dimension of bipartite graphs
- FPT algorithms for Token Jumping on Graphs
- Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid