On the Helly Property of Some Intersection Graphs

• Tanilson D. Santos UFRJ / UFT
• Jayme Szwarcfiter UFRJ
• Uéverton S. Souza UFF
• Claudson F. Bornstein UFRJ

DOI: https://doi.org/10.5753/ctd.2021.15752

Resumo

An EPG graph G is an edge-intersection graph of paths on a grid. In this thesis, we analyze structural characterizations and complexity aspects regarding EPG graphs. Our main focus is on the class of B₁-EPG graphs whose intersection model satisfies well-known the Helly property, called Helly-B₁-EPG. We show that the problem of recognizing Helly-B₁-EPG graphs is NP-complete. Besides, other intersection graph classes such as VPG, EPT, and VPT were also studied. We completely solve the problem of determining the Helly and strong Helly numbers of B_k-EPG graphs and B_k-VPG graphs for each non-negative integer k. Finally, we show that every Chordal B₁-EPG graph is at the intersection of VPT and EPT.

Palavras-chave: Helly property, Intersection graphs, NP-completeness

Referências

Alcón, L., Bonomo, F., Durán, G., Gutierrez, M., Mazzoleni, M. P., Ries, B., andValencia-Pabon, M. (2016). On the bend number of circular-arc graphs as edge in-tersection graphs of paths on a grid.Discrete Applied Mathematics, 234:12–21.

Asinowski, A. and Suk, A. (2009). Edge intersection graphs of systems of paths on a grid with a bounded number of bends. Discrete Applied Math, 157:3174–3180.

Bandy, M. and Sarrafzadeh, M. (1990). Stretching a knock-knee layout for multilayer wiring. IEEE Transactions on Computers, 39:148–151.

Cameron, K., Chaplick, S., and Hoàng, C. T. (2016). Edge intersection graphs of L-shaped paths in grids. Discrete Applied Mathematics, 210:185–194.

Cohen, E., Golumbic, M. C., and Ries, B. (2014). Characterizations of cographs as intersection graphs of paths on a grid. Discrete Applied Mathematics, 178:46–57.

Dourado, M. C., Protti, F., and Szwarcfiter, J. L. (2009). Complexity aspects of the Helly property: Graphs and hypergraphs. The Electronic Journal of Combinatorics, 17:1–53.

Golumbic, M. C. and Jamison, R. E. (1985). The edge intersection graphs of paths in a tree. Journal of Combinatorial Theory, B 38:8–22.

Golumbic, M. C., Lipshteyn, M., and Stern, M. (2009). Edge intersection graphs of single bend paths on a grid. Networks, 54:130–138.

Golumbic, M. C., Lipshteyn, M., and Stern, M. (2013). Single bend paths on a grid have strong Helly number 4. Networks, 62:161–163.

Golumbic, M. C. and Morgenstern, G. (2019). Edge intersection graphs of paths on a grid. In 50 years of Combinatorics, Graph Theory, and Computing, pages 193–209. Chapman and Hall/CRC.

Molitor, P. (1991). A survey on wiring. Journal of Information Processing and Cybernet-ics, EIK, 27:3–19.