Article in volume
Authors:
Title:
Relationship among $B_1$-EPG, VPT and EPT graphs classes
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 841-858
Received: 2020-06-22 , Revised: 2021-03-18 , Accepted: 2021-03-22 , Available online: 2021-05-11 , https://doi.org/10.7151/dmgt.2408
Abstract:
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
References:
- 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 - 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 - 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 - 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 - C.F. Bornstein, M.C. Golumbic, T.D. Santos, U.S. Souza and J.L. Szwarcfiter, The complexity of Helly-$B_{1}$-EPG graph recognition, Discrete Math. Theoret. Comput. Sci. 22 (2020) #19.
https://doi.org/10.23638/DMTCS-22-1-19 - E. Cela and E. Gaar, Monotonic representations of outerplanar graphs as edge intersection graphs of paths on a grid (2019).
arXiv: 1908.01981 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - F. Harary and C. Holzmann, Line graphs of bipartite graphs, Rev. Soc. Mat. Chile 1 (1974) 19–22.
- 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 - 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 - 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
Close