Sobre a Dificuldade de Reconhecimento de Grafos B1-EPG-Helly
Resumo
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 forma que dois vértices em G são adjacentes se e somente se os caminhos correspondentes em Q compartilham arestas. Se tais caminhos em Q tem no máximo k mudanças de direção (dobras), então a representação é dita 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.
Referências
Booth, K. and Lueker, G. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13:335–379.
Cohen, E., Golumbic, M. C., and Ries, B. (2014). Characterizations of cographs as intersection graphs of paths on a grid. Discrete Applied Mathematics, 178:46–57.
Golumbic, M., Lipshteyn, M., and Stern, M. (2009). Edge intersection graphs of single bend paths on a grid. Networks, 54:130–138.
Heldt, D., Knauer, K., and Ueckerdt, T. (2014). Edge-intersection graphs of grid paths: the bend-number. Discrete Appl. Math, 167:144–162.
Martin Pergel, P. R. (2017). On edge intersection graphs of paths with 2 bends. Discrete Applied Mathematics, 226:106–116.
Ries, B. (2009). Some properties of edge intersection graphs of single bend paths on a grid. Electronic Notes in Discrete Mathematics, 34:29–33.
