Identifying Subclasses of Helly B1-EPG Graphs

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 19. TAG – Teoria e Algoritmos em Grafos
  • Palavras chaves: EPG; PROPRIEDADE HELLY; DOBRA SIMPLES;
  • 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

Resumo

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.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!