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 条
  • [31] On Graphs of Order n with Metric Dimension n-4
    Wang, Juan
    Tian, Fenglei
    Liu, Yunlong
    Pang, Jingru
    Miao, Lianying
    GRAPHS AND COMBINATORICS, 2023, 39 (02)
  • [32] On the WL-dimension of circulant graphs of prime power order
    Ponomarenko, Ilia
    ALGEBRAIC COMBINATORICS, 2023, 6 (06):
  • [33] Complete intersection dimension
    Luchezar L. Avramov
    Vesselin N. Gasharov
    Irena V. Peeva
    Publications Mathématiques de l'Institut des Hautes Études Scientifiques, 1997, 86 (1): : 67 - 114
  • [34] COMPLETE INTERSECTION DIMENSION
    Avramov, Luchezar L.
    Gasharov, Vesseln N.
    Peeva, Irena V.
    PUBLICATIONS MATHEMATIQUES, 1997, (86): : 67 - 114
  • [35] Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs
    Nikoletseas, Sotiris
    Raptopoulos, Christoforos
    Spirakis, Paul G.
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2012, 2012, 7464 : 728 - 739
  • [36] Maximum cliques in graphs with small intersection number and random intersection graphs
    Nikoletseas, Sotiris E.
    Raptopoulos, Christoforos L.
    Spirakis, Paul G.
    COMPUTER SCIENCE REVIEW, 2021, 39
  • [37] Complete Intersection Flat Dimension and the Intersection Theorem
    Sahandi, Parviz
    Sharif, Tirdad
    Yassemi, Siamak
    ALGEBRA COLLOQUIUM, 2012, 19 : 1161 - 1166
  • [38] On the hyperbolicity of bipartite graphs and intersection graphs
    Coudert, David
    Ducoffe, Guillaume
    DISCRETE APPLIED MATHEMATICS, 2016, 214 : 187 - 195
  • [39] INTERSECTION GRAPHS OF CONCATENABLE SUBTREES OF GRAPHS
    GAVRIL, F
    URRUTIA, J
    DISCRETE APPLIED MATHEMATICS, 1994, 52 (02) : 195 - 209
  • [40] Chordal graphs as intersection graphs of pseudosegments
    Dangelmayr, Cornelia
    Felsner, Stefan
    GRAPH DRAWING, 2007, 4372 : 208 - +
12345