Geodesic
Relationship among B1-EPG, VPT and EPT graphs classes
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 841-858 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

This research contains as a main result the proof that every chordal B_1-EPG graph is simultaneously in the graph classes VPT and EPT. In addition, we describe structures that must be present in any B_1-EPG graph which does not admit a Helly-B_1-EPG representation. In particular, this paper presents some features of non-trivial families of graphs properly contained in Helly-B_1-EPG, namely bipartite, block, cactus and line graphs of bipartite graphs.
Keywords: edge-intersection of paths on a grid, edge-intersection graph of paths in a tree, Helly property, intersection graphs, single bend paths, vertex-intersection graph of paths in a tree 
@article{DMGT_2023_43_3_a16,
     author = {Alc\'on, Liliana and Mazzoleni, Mar{\'\i}a P{\'\i}a and Dias dos Santos, Tanilson},
     title = {Relationship among {B1-EPG,} {VPT} and {EPT} graphs classes},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {841--858},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a16/}
}
TY  - JOUR
AU  - Alcón, Liliana
AU  - Mazzoleni, María Pía
AU  - Dias dos Santos, Tanilson
TI  - Relationship among B1-EPG, VPT and EPT graphs classes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 841
EP  - 858
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a16/
LA  - en
ID  - DMGT_2023_43_3_a16
ER  - 
%0 Journal Article
%A Alcón, Liliana
%A Mazzoleni, María Pía
%A Dias dos Santos, Tanilson
%T Relationship among B1-EPG, VPT and EPT graphs classes
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 841-858
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a16/
%G en
%F DMGT_2023_43_3_a16
Alcón, Liliana; Mazzoleni, María Pía; Dias dos Santos, Tanilson. Relationship among B1-EPG, VPT and EPT graphs classes. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 841-858. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a16/

[1] L. Alcón, M. Gutierrez and M.P. Mazzoleni, Recognizing vertex intersection graphs of paths on bounded degree trees, Discrete Appl. Math. 162 (2014) 70–77. https://doi.org/10.1016/j.dam.2013.08.004

[2] L. Alcón, M. Gutierrez and M.P. Mazzoleni, Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs, Discrete Math. 338 (2015) 103–110. https://doi.org/10.1016/j.disc.2014.08.020

[3] A. Asinowski and B. Ries, Some properties of edge intersection graphs of single-bend paths on a grid, Discrete Math. 312 (2012) 427–440. https://doi.org/10.1016/j.disc.2011.10.005

[4] A. Asinowski and A. Suk, Edge intersection graphs of systems of paths on a grid with a bounded number of bends, Discrete Appl. Math. 157 (2009) 3174–3180. https://doi.org/10.1016/j.dam.2009.06.015

[5] C.F. Bornstein, M.C. Golumbic, T.D. Santos, U.S. Souza and J.L. Szwarcfiter, The complexity of Helly-B1-EPG graph recognition, Discrete Math. Theoret. Comput. Sci. 22 (2020) #19. https://doi.org/10.23638/DMTCS-22-1-19

[6] E. Cela and E. Gaar, Monotonic representations of outerplanar graphs as edge intersection graphs of paths on a grid (2019). arXiv: 1908.01981

[7] E. Cohen, and M.C. Golumbic and B. Ries, Characterizations of cographs as intersection graphs of paths on a grid, Discrete Appl. Math. 178 (2014) 46–57. https://doi.org/10.1016/j.dam.2014.06.020

[8] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B 16 (1974) 47–56. https://doi.org/10.1016/0095-8956(74)90094-X

[9] F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211–227. https://doi.org/10.1016/0012-365X(78)90003-1

[10] M.C. Golumbic and R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151–159. https://doi.org/10.1016/0012-365X(85)90043-3

[11] M.C. Golumbic and R.E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B 38 (1985) 8–22. https://doi.org/10.1016/0095-8956(85)90088-7

[12] M.C. Golumbic, M. Lipshteyn and M. Stern, Edge intersection graphs of single bend paths on a grid, Networks 54 (2009) 130–138. https://doi.org/10.1002/net.20305

[13] M.C. Golumbic, M. Lipshteyn and M. Stern, Single bend paths on a grid have strong Helly number 4, Networks 62 (2013) 161–163. https://doi.org/10.1002/net.21509

[14] M.C. Golumbic, G. Morgenstern and D. Rajendraprasad, Edge-intersection graphs of boundary-generated paths in a grid, Discrete Appl. Math. 236 (2018) 214–222. https://doi.org/10.1016/j.dam.2017.10.014

[15] M.C. Golumbic and B. Ries, On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, Graphs Combin. 29 (2013) 499–517. https://doi.org/10.1007/s00373-012-1133-7

[16] F. Harary and C. Holzmann, Line graphs of bipartite graphs, Rev. Soc. Mat. Chile 1 (1974) 19–22.

[17] D. Heldt, K. Knauer and T. Ueckerdt, On the bend-number of planar and outerplanar graphs, Discrete Appl. Math. 179 (2014) 109–119. https://doi.org/10.1016/j.dam.2014.07.015

[18] B. Lévêque, F. Maffray and M. Preissmann, Characterizing path graphs by forbidden induced subgraphs, J. Graph Theory 62 (2009) 369–384. https://doi.org/10.1002/jgt.20407

[19] M.M. Sysło, Triangulated edge intersection graphs of paths in a tree, Discrete Math. 55 (1985) 217–220. https://doi.org/10.1016/0012-365X(85)90050-0