Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid

被引：0
|
作者：
Chaplick, Steven [1 ]
Cohen, Elad [2 ]
Stacho, Juraj [2 ]
机构：
[1] Univ Toronto, Dept Comp Sci, 10 Kings Coll Rd, Toronto, ON M5S 3G4, Canada
[2] Univ Haifa, Caesarea Rothschild Inst, IL-31905 Haifa, Israel
来源：
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE | 2011年 / 6986卷
关键词：
INTERVAL GRAPHS; TREE;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, known as B-0-VPG graphs. Recognizing these graphs is an NP-hard problem. In light of this, we focus on their subclasses. In the paper, we describe polynomial time algorithms for recognizing chordal B-0-VPG graphs, and for recognizing B-0-VPG graphs that have a representation on a grid with 2 rows.
引用
收藏
页码：319 / +
页数：2
相关论文
共 24 条
  • [1] Some properties of edge intersection graphs of single-bend paths on a grid
    Asinowski, A.
    Ries, B.
    DISCRETE MATHEMATICS, 2012, 312 (02) : 427 - 440
  • [2] Edge Intersection Graphs of Single Bend Paths on a Grid
    Golumbic, Martin Charles
    Lipshteyn, Marina
    Stern, Michal
    NETWORKS, 2009, 54 (03) : 130 - 138
  • [3] Recognizing vertex intersection graphs of paths on bounded degree trees
    Alcon, L.
    Gutierrez, M.
    Mazzoleni, M. P.
    DISCRETE APPLIED MATHEMATICS, 2014, 162 : 70 - 77
  • [4] Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs
    Alcon, Liliana
    Bonomo, Flavia
    Mazzoleni, Maria Pia
    GRAPHS AND COMBINATORICS, 2017, 33 (04) : 653 - 664
  • [5] Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs
    Liliana Alcón
    Flavia Bonomo
    María Pía Mazzoleni
    Graphs and Combinatorics, 2017, 33 : 653 - 664
  • [6] Edge-intersection graphs of grid paths: The bend-number
    Heldt, Daniel
    Knauer, Kolja
    Ueckerdt, Torsten
    DISCRETE APPLIED MATHEMATICS, 2014, 167 : 144 - 162
  • [7] On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
    Alcon, Liliana
    Bonomo, Flavia
    Duran, Guillermo
    Gutierrez, Marisa
    Mazzoleni, Maria Pia
    Ries, Bernard
    Valencia-Pabon, Mario
    DISCRETE APPLIED MATHEMATICS, 2018, 234 : 12 - 21
  • [8] On k-bend and monotonic l-bend edge intersection graphs of paths on a grid
    Cela, Eranda
    Gaar, Elisabeth
    DISCRETE APPLIED MATHEMATICS, 2023, 331 : 88 - 103
  • [9] INTERSECTION GRAPHS OF VERTEX DISJOINT PATHS IN A TREE
    PANDA, BS
    MOHANTY, SP
    DISCRETE MATHEMATICS, 1995, 146 (1-3) : 179 - 209
  • [10] Vertex Contact Graphs of Paths on a Grid
    Aerts, Nieke
    Felsner, Stefan
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2014, 8747 : 56 - 68
123