10.23638/DMTCS-22-1-19
https://dmtcs.episciences.org/5603
Bornstein, Claudson F.
Claudson F.
Bornstein
Golumbic, Martin Charles
Martin Charles
Golumbic
Santos, Tanilson D.
Tanilson D.
Santos
Souza, Uéverton S.
Uéverton S.
Souza
Szwarcfiter, Jayme L.
Jayme L.
Szwarcfiter
The Complexity of Helly-$B_{1}$ EPG Graph Recognition
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.
episciences.org
Computer Science - Discrete Mathematics
Computer Science - Computational Complexity
Computer Science - Data Structures and Algorithms
arXiv.org - Non-exclusive license to distribute
2020-06-04
2020-06-04
2020-06-04
eng
journal article
arXiv:1906.11185
10.48550/arXiv.1906.11185
1365-8050
10.48550/arxiv.1906.11185
https://dmtcs.episciences.org/5603/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 22 no. 1
Graph Theory
Researchers
Students