DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

L. Alcón

Liliana Alcón

email: liliana@mate.unlp.edu.ar

M.P. Mazzoleni

Maria Mazzoleni

8

email: pia@mate.unlp.edu.ar

T.D. Santos

Tanilson Santos

Federal University of Tocantins

email: tanilson.dias@mail.uft.edu.br

Title:

Relationship among $B_1$-EPG, VPT and EPT graphs classes

PDF

Source:

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:

  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-$B_{1}$-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

Close