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 条
  • [1] Grid Intersection Graphs and Order Dimension
    Chaplick, Steven
    Felsner, Stefan
    Hoffmann, Udo
    Wiechert, Veit
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2018, 35 (02): : 363 - 391
  • [2] Ferrers dimension of grid intersection graphs
    Chaplick, Steven
    Hell, Pavol
    Otachi, Yota
    Saitoh, Toshiki
    Uehara, Ryuhei
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 130 - 135
  • [3] ON GRID INTERSECTION GRAPHS
    HARTMAN, IBA
    NEWMAN, I
    ZIV, R
    DISCRETE MATHEMATICS, 1991, 87 (01) : 41 - 52
  • [4] Asymptotic dimension of intersection graphs
    Dvorak, Zdenek
    Norin, Sergey
    EUROPEAN JOURNAL OF COMBINATORICS, 2025, 123
  • [5] Intersection Dimension of Bipartite Graphs
    Chaplick, Steven
    Hell, Pavol
    Otachi, Yota
    Saitoh, Toshiki
    Uehara, Ryuhei
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014), 2014, 8402 : 323 - 340
  • [6] GRID INTERSECTION GRAPHS AND BOXICITY
    BELLANTONI, S
    HARTMAN, IB
    PRZYTYCKA, T
    WHITESIDES, S
    DISCRETE MATHEMATICS, 1993, 114 (1-3) : 41 - 49
  • [7] Grid intersection and box intersection graphs on surfaces - Extended abstract
    Kratochvil, J
    Przytycka, T
    GRAPH DRAWING, 1996, 1027 : 365 - 372
  • [8] Proper circular arc graphs as intersection graphs of paths on a grid
    Galby, Esther
    Pia Mazzoleni, Maria
    Ries, Bernard
    DISCRETE APPLIED MATHEMATICS, 2019, 262 : 195 - 202
  • [9] Interval bigraphs are unit grid intersection graphs
    Richerby, David
    DISCRETE MATHEMATICS, 2009, 309 (06) : 1718 - 1719
  • [10] Characterizations of cographs as intersection graphs of paths on a grid
    Cohen, Elad
    Golumbic, Martin Charles
    Ries, Bernard
    DISCRETE APPLIED MATHEMATICS, 2014, 178 : 46 - 57
12345