Identifying Subclasses of Helly B1-EPG Graphs

Download
Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 19. TAG – Teoria e Algoritmos em Grafos
  • Keywords: EPG; PROPRIEDADE HELLY; DOBRA SIMPLES;

Authors:

  • 1 UNIVERSIDADE NACIONAL DE LA PLATA - UNLP
  • 2 UNIVERSIDAD NACIONAL DE LA PLATA - UNLP
  • 3 Universidade Federal do Rio de Janeiro

Identifying Subclasses of Helly B1-EPG Graphs

Tanilson Dias dos Santos

Universidade Federal do Rio de Janeiro

Abstract

Este trabalho apresenta estruturas presentes em qualquer subgrafo induzido B1-EPG que não admita uma representação B1-EPG-Helly. Por meio dessas estruturas foi possível delimitar alguns conjuntos de subgrafos que definem subfamílias Helly. Em particular, essa pesquisa apresenta uma caracterização para algumas famílias não triviais de grafos que estão propriamente contidas na classe de grafos B1-EPG-Helly. Nomeadamente essas famílias são as dos grafos Bipartidos, Blocos, Cactus e Linha de Bipartido.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!