Article in volume
Authors:
Title:
Helly and strong Helly numbers of $B_k$-EPG and $B_k$-VPG graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1237-1252
Received: 2020-05-15 , Revised: 2021-07-13 , Accepted: 2021-07-14 , Available online: 2021-08-03 , https://doi.org/10.7151/dmgt.2427
Abstract:
EPG graphs were introduced by Golumbic, Lypshteyn, and Stern in 2009 and consist
of the intersection graphs of sets of paths on the orthogonal grid, whose
intersections are taken considering the edges of the paths. If the intersections
of the paths consider the vertices and not the edges, the resulting graph class
is called VPG graphs. A path $P$ is a $B_k$-path if it contains at most $k$
bends. $B_k$-EPG and $B_k$-VPG graphs are the intersection graphs of $B_k$-paths
on the orthogonal grid, considering the intersection of edges and vertices,
respectively. A family $\cal{F}$ is $h$-Helly when every $h$-intersecting
subfamily $\cal{F'}$ of it satisfies $core(\cal{F'})\neq\emptyset$. If for every
subfamily $\cal{F'}$ of $\cal{F}$, there are $h$ subsets whose core equals the
core of $\cal {F'}$, then $\cal {F}$ is said to be {strong} $h$-{Helly}.
The Helly number of the family $\cal{F}$ is the least integer $h$, such that
$\cal{F}$ is $h$-Helly. Similarly, the strong Helly number of $\cal{F}$ is
the least $h$, for which $\cal{F}$ is strong $h$-Helly. In this paper, we solve
the problem of determining both the Helly and strong Helly numbers, for
$B_k$-EPG, and $B_k$-VPG graphs, for each value $k$.
Keywords:
EPG, VPG, path, grid, bend, Helly number, strong Helly
References:
- A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn and M. Stern, String graphs of $k$-bend paths on a grid, Electron. Notes Discrete Math. 37 (2011) 141–146.
https://doi.org/10.1016/j.endm.2011.05.025 - A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn and M. Stern, Vertex intersection graphs of paths on a grid, J. Graph Algorithms Appl. 16 (2012) 129–150.
https://doi.org/10.7155/jgaa.00253 - C. Berge and P. Duchet, A generalization of Gilmore's theorem, in: Recent Advances in Graph Theory, M. Fiedler (Ed(s)), (Acad. Praha, Prague 1975) 49–55.
- 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. Theor. Comput. Sci. 22 (2020) #19.
https://doi.org/10.23638/DMTCS-22-1-19 - M.C. Dourado, M.C. Lin, F. Protti and J.L. Szwarcfiter, Improved algorithms for recognizing $p$-Helly and hereditary $p$-Helly hypergraphs, Inform. Process. Lett. 108 (2008) 247–250.
https://doi.org/10.1016/j.ipl.2008.05.013 - M.C. Dourado, F. Protti and J.L. Szwarcfiter, On the strong $p$-Helly property, Discrete Appl. Math. 156 (2008) 1053–1057.
https://doi.org/10.1016/j.dam.2007.05.047 - M.C. Dourado, F. Protti and J.L. Szwarcfiter, Complexity aspects of the Helly property: graphs and hypergraphs, Electron. J. Combin. (2009) #DS17.
https://doi.org/10.37236/38 - P. Duchet, Proprieté de Helly et problèmes de représentations, Problémes Combinatoires et Théorie de Graphs, Colloquium International CNRS 260 (1978) 117–118.
- 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$: errata atque emendationes ad ``edge intersection graphs of single bend paths on a grid'', Networks 62 (2013) 161–163.
https://doi.org/10.1002/net.21509 - M.C. Golumbic and G. Morgenstern, Edge intersection graphs of paths on a grid, in: 50 Years of Combinatorics, Graph Theory, and Computing, F. Chung, R. Graham, F. Hoffman, L. Hogben, R. Mullin and D. West (Ed(s)), (Chapman and Hall/CRC 2019) 193–209.
- J. Kratochv{\'\i}l, String graphs. II. Recognizing string graphs is NP-hard, J. Combin. Theory Ser. B 52 (1991) 67–78.
https://doi.org/10.1016/0095-8956(91)90091-W - M. Schaefer, E. Sedgwick and D. Štefankovič, Recognizing string graphs in NP, J. Comput. System Sci. 67 (2003) 365–380.
https://doi.org/10.1016/S0022-0000(03)00045-X
Close