Geodesic
The Complexity of Helly-$B_{1}$ EPG Graph Recognition
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.23638/DMTCS-22-1-19
Classification : 05C38 
@article{DMTCS_2020_22_1_a14,
     author = {Bornstein, Claudson F. and Golumbic, Martin Charles and Santos, Tanilson D. and Souza, U\'everton S. and Szwarcfiter, Jayme L.},
     title = {The {Complexity} of {Helly-}$B_{1}$ {EPG} {Graph} {Recognition}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-19},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-19/}
}
TY  - JOUR
AU  - Bornstein, Claudson F.
AU  - Golumbic, Martin Charles
AU  - Santos, Tanilson D.
AU  - Souza, Uéverton S.
AU  - Szwarcfiter, Jayme L.
TI  - The Complexity of Helly-$B_{1}$ EPG Graph Recognition
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-19/
DO  - 10.23638/DMTCS-22-1-19
LA  - en
ID  - DMTCS_2020_22_1_a14
ER  - 
%0 Journal Article
%A Bornstein, Claudson F.
%A Golumbic, Martin Charles
%A Santos, Tanilson D.
%A Souza, Uéverton S.
%A Szwarcfiter, Jayme L.
%T The Complexity of Helly-$B_{1}$ EPG Graph Recognition
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-19/
%R 10.23638/DMTCS-22-1-19
%G en
%F DMTCS_2020_22_1_a14
Bornstein, Claudson F.; Golumbic, Martin Charles; Santos, Tanilson D.; Souza, Uéverton S.; Szwarcfiter, Jayme L. The Complexity of Helly-$B_{1}$ EPG Graph Recognition. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi: 10.23638/DMTCS-22-1-19

Cité par Sources :