Geodesic
The Complexity of Helly-$B_{1}$ EPG Graph Recognition
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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},
     year = {2020-2021},
     volume = {22},
     number = {1},
     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
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
%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 :