On the Helly Property of Some Intersection Graphs - Santos, Tanilson D.; Szwarcfiter, Jayme; Souza, Uéverton S.; Bornstein, Claudson F. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2021: Anais do XXXIV Concurso de Teses e Dissertações, 2021)
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 1 -EPG graphs whose intersection model satisfies well-known the Helly property, called Helly-B 1 -EPG. We show that the problem of recognizing Helly-B 1 -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 1 -EPG graph is at the intersection of VPT and EPT.