CPS845/MAE473, Tópicos Especiais em Teoria dos Grafos
Professora Márcia
R. Cerioli
Classes de Grafos de Interseção:
- Grafos de indiferença (Grafos de Intervalo Proprio = Grafos de Intervalo Unitario). [Thiago]
- Grafos de retângulos no plano (boxicity two graphs).
- Grafos de permutação. [Eduardo]
- Grafos círculo - interseção de cordas de um
círculo. [Guilherme]
- Grafos UV - interseção de caminhos em árvore. [Rodrigo]
- Grafos UE - interseção em arestas de caminhos em árvore
- Grafos UEH - interseção em arestas de família Helly de caminhos em árvore
- Grafos de vizinhança - interseção da vizinhança
aberta ou fechada.
- Grafos arco-circular Helly.
- Grafos arco-circular próprio.
- Grafos arco-circular unitário.
- Grafos string - interseção de curvas no plano.
- Grafos disco unitário - grafo de interseção
de círculos de raio 1 no plano.
- Grafos clique [Rafael]
- ...
ISGCI - Information
System on Graph Class Inclusions
Roteiro para a monografia/seminário/slides:
Definição da classe, exemplos e contra-exemplos, teoremas
de caracterização e reconhecimento e relação com
outras classes de grafos. Problemas conhecidos já estudados para a
classe (ciclo hamiltoniano, clique máxima, árvore de steiner,
coloração, ...)
A monografia/slides deve incluir a prova detalhada de pelo menos dois teoremas de resultados estruturais
e as referências utilizadas.
Cópia eletrônica das referências usadas. Busque pelas versões oficiais das publicações,
Prazo: primeira versão monografia/slides (que já deve ter o roteiro completo com os pontos a serem ainda completados com detalhes): 3 de dezembro.
Versão completa da monografia: 17 de dezembro
Prazo: prévia da versão slides (só de quem não vai entregar monografia): 28 de novembro.
versão slides: no dia do seminário.
Criada em 2 nov 25 e atualizada em 5 nov 2025 por Márcia R. Cerioli