episciences.org_5603_1675651012
1675651012
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
06
04
2020
vol. 22 no. 1
Graph Theory
The Complexity of Helly$B_{1}$ EPG Graph Recognition
Claudson F.
Bornstein
Martin Charles
Golumbic
Tanilson D.
Santos
UĂ©verton S.
Souza
Jayme L.
Szwarcfiter
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 subcollection 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 edgeintersections of paths satisfy the Helly property, socalled
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 NPcomplete, and it remains NPcomplete even when
restricted to 2apex and 3degenerate graphs.
06
04
2020
5603
https://arxiv.org/licenses/nonexclusivedistrib/1.0
arXiv:1906.11185
10.48550/arXiv.1906.11185
https://arxiv.org/abs/1906.11185v2
https://arxiv.org/abs/1906.11185v1
10.23638/DMTCS22119
https://dmtcs.episciences.org/5603

https://dmtcs.episciences.org/6506/pdf

https://dmtcs.episciences.org/6506/pdf