Geodesic
Vertex Intersection Graphs of Paths on a Grid
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 129-150.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We investigate the class of vertex intersection graphs of paths on a grid, and specifically consider the subclasses that are obtained when each path in the representation has at most k bends (turns). We call such a subclass the Bk-VPG graphs, k ≥ 0. In chip manufacturing, circuit layout is modeled as paths (wires) on a grid, where it is natural to constrain the number of bends per wire for reasons of feasibility and to reduce the cost of the chip. If the number k of bends is not restricted, then the VPG graphs are equivalent to the well-known class of string graphs, namely, the intersection graphs of arbitrary curves in the plane. In the case of B0-VPG graphs, we observe that horizontal and vertical segments have strong Helly number 2, and thus the clique problem has polynomial-time complexity, given the path representation. The recognition and coloring problems for B0-VPG graphs, however, are NP-complete. We give a 2-approximation algorithm for coloring B0-VPG graphs. Furthermore, we prove that triangle-free B0-VPG graphs are 4-colorable, and this is best possible. We present a hierarchy of VPG graphs relating them to other known families of graphs. The grid intersection graphs are shown to be equivalent to the bipartite B0-VPG graphs and the circle graphs are strictly contained in B1-VPG. We prove the strict containment of B0-VPG into B1-VPG, and we conjecture that, in general, this strict containment continues for all values of k. We present a graph which is not in B1-VPG. Planar graphs are known to be in the class of string graphs, and we prove here that planar graphs are B3-VPG graphs, although it is not known if this is best possible.
DOI : 10.7155/jgaa.00253
Keywords: String Graphs, Planar Graphs, Circle Graphs, Chordal Graphs, Grid Intersection Graphs, Triangle-free Graphs, Graph Coloring, Helly Property 
@article{JGAA_2012_16_2_a0,
     author = {Andrei Asinowski and Elad Cohen and Martin Charles Golumbic and Vincent Limouzy and Marina Lipshteyn and Michal Stern},
     title = {Vertex {Intersection} {Graphs} of {Paths} on a {Grid}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {129--150},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00253},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00253/}
}
TY  - JOUR
AU  - Andrei Asinowski
AU  - Elad Cohen
AU  - Martin Charles Golumbic
AU  - Vincent Limouzy
AU  - Marina Lipshteyn
AU  - Michal Stern
TI  - Vertex Intersection Graphs of Paths on a Grid
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 129
EP  - 150
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00253/
DO  - 10.7155/jgaa.00253
LA  - en
ID  - JGAA_2012_16_2_a0
ER  - 
%0 Journal Article
%A Andrei Asinowski
%A Elad Cohen
%A Martin Charles Golumbic
%A Vincent Limouzy
%A Marina Lipshteyn
%A Michal Stern
%T Vertex Intersection Graphs of Paths on a Grid
%J Journal of Graph Algorithms and Applications
%D 2012
%P 129-150
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00253/
%R 10.7155/jgaa.00253
%G en
%F JGAA_2012_16_2_a0
Andrei Asinowski; Elad Cohen; Martin Charles Golumbic; Vincent Limouzy; Marina Lipshteyn; Michal Stern. Vertex Intersection Graphs of Paths on a Grid. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 129-150. doi : 10.7155/jgaa.00253. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00253/

Cité par Sources :