1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Relationship among B1-EPG, VPT and EPT Graphs Classes

Published Online: 17 Jun 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 22 Jun 2020
Accepted: 22 Mar 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

This research contains as a main result the proof that every chordal B1-EPG graph is simultaneously in the graph classes VPT and EPT. In addition, we describe structures that must be present in any B1-EPG graph which does not admit a Helly-B1-EPG representation. In particular, this paper presents some features of non-trivial families of graphs properly contained in Helly-B1-EPG, namely bipartite, block, cactus and line graphs of bipartite graphs.

Keywords

MSC 2010

[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.00410.1016/j.dam.2013.08.004Search in Google Scholar

[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.02010.1016/j.disc.2014.08.020Search in Google Scholar

[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.00510.1016/j.disc.2011.10.005Search in Google Scholar

[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.01510.1016/j.dam.2009.06.015Search in Google Scholar

[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-19Search in Google Scholar

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

[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.02010.1016/j.dam.2014.06.020Search in Google Scholar

[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-X10.1016/0095-8956(74)90094-XSearch in Google Scholar

[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-110.1016/0012-365X(78)90003-1Search in Google Scholar

[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-310.1016/0012-365X(85)90043-3Search in Google Scholar

[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-710.1016/0095-8956(85)90088-7Search in Google Scholar

[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.2030510.1002/net.20305Search in Google Scholar

[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.2150910.1002/net.21509Search in Google Scholar

[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.01410.1016/j.dam.2017.10.014Search in Google Scholar

[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-710.1007/s00373-012-1133-7Search in Google Scholar

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

[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.01510.1016/j.dam.2014.07.015Search in Google Scholar

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo