A Complexidade do Reconhecimento de Grafos B1-EPG-Helly

Golumbic, Lipshteyn e Stern definiram em 2009 os grafos EPG, uma classe de grafos
de intersecção baseada na intersecção de arestas de caminhos em uma grade. Um grafo EPG G é um grafo que admite um esquema de representação onde seus vértices são representados por caminhos de uma grade Q, de tal forma que dois vértices em G são adjacentes se e somente se seus caminhos correspondentes em Q possuem arestas em comum. Quando tais caminhos em Q possuem no máximo k mudanças de direção (dobras), dizemos que esta é uma representação Bk-EPG.
Uma coleção C de conjuntos satisfaz a propriedade Helly quando toda subcoleção de C que é mutuamente intersectante possui pelo menos um elemento comum. Neste trabalho mostramos que o reconhecimento de grafos que admitem representação B1-EPG satisfazendo a propriedade Helly é NP-difícil.