Intersection dimension of bipartite graphs

• Steven Chaplick

  Institut fur Mathematik, Technische Universitat Berlin

• Pavol Hell

  School of Computing Science, Simon Fraser University

• Yota Otachi

  School of Information Science, Japan Advanced Institute of Science and Technology

• Toshiki Saitoh

  Graduate School of Engineering, Kobe University

• Ryuhei Uehara

  School of Information Science, Japan Advanced Institute of Science and Technology

抄録

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.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 2014 (4), 1-7, 2014-06-06

  一般社団法人情報処理学会

詳細情報

• CRID: 1574231877583849088
• NII論文ID: 110009785564
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: en
• データソース種別:
  • CiNii Articles