Grid Intersection Graphs and Order Dimension

被引:0
|
作者
Steven Chaplick
Stefan Felsner
Udo Hoffmann
Veit Wiechert
机构
[1] Technische Universität Berlin,Institut für Mathematik
来源
Order | 2018年 / 35卷
关键词
Order dimension; Grid intersection graphs;
D O I
暂无
中图分类号
学科分类号
摘要
We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation on these classes. Order dimension plays a role in many arguments.
引用
收藏
页码:363 / 391
页数:28
相关论文
共 50 条
  • [41] COMPARABILITY-GRAPHS AND INTERSECTION GRAPHS
    GOLUMBIC, MC
    ROTEM, D
    URRUTIA, J
    DISCRETE MATHEMATICS, 1983, 43 (01) : 37 - 46
  • [42] Intersection graphs of pseudosegments: Chordal graphs
    Dangelmayr C.
    Felsner S.
    Trotter W.T.
    Journal of Graph Algorithms and Applications, 2010, 14 (02) : 199 - 220
  • [43] Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
    Chaplick, Steven
    Cohen, Elad
    Stacho, Juraj
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2011, 6986 : 319 - +
  • [44] INTERSECTION GRAPHS OF R-GRAPHS
    GARDNER, ML
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 23 (07): : A655 - A655
  • [45] Subspace intersection graphs
    Laison, Joshua D.
    Qing, Yulan
    DISCRETE MATHEMATICS, 2010, 310 (23) : 3413 - 3416
  • [46] INTERSECTION THEORY FOR GRAPHS
    BRYLAWSKI, T
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 30 (02) : 233 - 246
  • [47] Modular intersection graphs
    McMorris, FR
    Wang, C
    GRAPHS AND COMBINATORICS, 1996, 12 (03) : 267 - 281
  • [48] INTERSECTION OF RANDOM GRAPHS
    KLIMOV, GP
    HARRISON, W
    DOKLADY AKADEMII NAUK SSSR, 1988, 302 (04): : 799 - 802
  • [49] Signed intersection graphs
    Acharya, B. D.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2010, 13 (06): : 553 - 569
  • [50] FUZZY INTERSECTION GRAPHS
    MCALLISTER, MLN
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1988, 15 (10) : 871 - 886