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 条
  • [21] Edge version of metric dimension for the families of grid graphs and generalized prism graphs
    Nasir, Ruby
    Zahid, Zohaib
    Zafar, Sohail
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (03)
  • [22] Metric and strong metric dimension in intersection power graphs of finite groups
    Ma, Xuanlong
    Fu, Ruiqin
    COMMUNICATIONS IN ALGEBRA, 2025, 53 (05) : 1829 - 1840
  • [23] Edge-intersection graphs of boundary-generated paths in a grid
    Golumbic, Martin Charles
    Morgenstern, Gila
    Rajendraprasad, Deepak
    DISCRETE APPLIED MATHEMATICS, 2018, 236 : 214 - 222
  • [24] Edge intersection graphs of systems of paths on a grid with a bounded number of bends
    Asinowski, Andrei
    Suk, Andrew
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (14) : 3174 - 3180
  • [25] Edge-intersection graphs of grid paths: The bend-number
    Heldt, Daniel
    Knauer, Kolja
    Ueckerdt, Torsten
    DISCRETE APPLIED MATHEMATICS, 2014, 167 : 144 - 162
  • [26] On the robustness of the metric dimension of grid graphs to adding a single edge
    Mashkaria, Satvik
    Odor, Gergely
    Thiran, Patrick
    DISCRETE APPLIED MATHEMATICS, 2022, 316 : 1 - 27
  • [27] Graphs whose mixed metric dimension is equal to their order
    Ghalavand, Ali
    Klavzar, Sandi
    Tavakoli, Mostafa
    COMPUTATIONAL & APPLIED MATHEMATICS, 2023, 42 (05):
  • [28] Graphs whose mixed metric dimension is equal to their order
    Ali Ghalavand
    Sandi Klavžar
    Mostafa Tavakoli
    Computational and Applied Mathematics, 2023, 42
  • [29] Graphs of Order n with Partition Dimension n - 3
    Haryeni, Debi Oktia
    Ridwan, Muhammad
    Baskoro, Edy Tri
    IAENG International Journal of Applied Mathematics, 2023, 53 (01)
  • [30] Some properties of edge intersection graphs of single-bend paths on a grid
    Asinowski, A.
    Ries, B.
    DISCRETE MATHEMATICS, 2012, 312 (02) : 427 - 440
12345