On the Helly Property of Some Intersection Graphs
ResumoAn 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 B1-EPG graphs whose intersection model satisfies well-known the Helly property, called Helly-B1-EPG. We show that the problem of recognizing Helly-B1-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 Bk-EPG graphs and Bk-VPG graphs for each non-negative integer k. Finally, we show that every Chordal B1-EPG graph is at the intersection of VPT and EPT.
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.