{"docId":6506,"paperId":5603,"url":"https:\/\/dmtcs.episciences.org\/5603","doi":"10.23638\/DMTCS-22-1-19","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":372,"name":"vol. 22 no. 1"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"1906.11185","repositoryVersion":3,"repositoryLink":"https:\/\/arxiv.org\/abs\/1906.11185v3","dateSubmitted":"2019-06-27 03:32:54","dateAccepted":"2020-06-04 16:56:23","datePublished":"2020-06-04 16:56:38","titles":["The Complexity of Helly-$B_{1}$ EPG Graph Recognition"],"authors":["Bornstein, Claudson F.","Golumbic, Martin Charles","Santos, Tanilson D.","Souza, U\u00e9verton S.","Szwarcfiter, Jayme L."],"abstracts":["Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph $G$ is a graph that admits a representation where its vertices correspond to paths in a grid $Q$, such that two vertices of $G$ are adjacent if and only if their corresponding paths in $Q$ have a common edge. If the paths in the representation have at most $k$ bends, we say that it is a $B_k$-EPG representation. A collection $C$ of sets satisfies the Helly property when every sub-collection of $C$ that is pairwise intersecting has at least one common element. In this paper, we show that given a graph $G$ and an integer $k$, the problem of determining whether $G$ admits a $B_k$-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-$B_k$-EPG representation, is in NP, for every $k$ bounded by a polynomial function of $|V(G)|$. Moreover, we show that the problem of recognizing Helly-$B_1$-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs."],"keywords":["Computer Science - Discrete Mathematics","Computer Science - Computational Complexity","Computer Science - Data Structures and Algorithms"]}