CPS845/MAB723, Tópicos Especiais em Teoria dos Grafos
Professora Márcia
R. Cerioli
Classes de Grafos de Interseção:
- Grafos de indiferença.
- Grafos de retângulos no plano (boxicity two graphs).
- Grafos de permutação. [Thiago]
- Grafos PI - interseção de triângulos entre duas retas paralelas.
- Grafos de trapézios - interseção de trapézios entre duas retas paralelas
- Grafos círculo - interseção de cordas de um
círculo. [Aline]
- Grafos UV - interseção de caminhos em árvore.
- Grafos RDV=RDE - interseção de caminhos em árvore
enraizada. - [Paloma]
- Grafos UE - interseção em arestas de caminhos em árvore
- Grafos UEH - interseção em arestas de família de caminhos Helly em árvore
- Grafos de vizinhança - interseção da vizinhança
aberta ou fechada.
- Grafos arco-circular.
- Grafos arco-circular Helly. [Rômulo]
- Grafos arco-circular próprios.
- Grafos arco-circular unitário.
- Grafos Threshold. [Alexsander]
- Grafos BIG - block intersection graphs.
- Grafos string - interseção de curvas no plano. [Rodrigo]
- Grafos 2-DIR (2-DIR-PURO) - Grafos de interseção de
segmentos paralelos no plano em no máximo duas direções
(segmentos paralelos são disjuntos).
- Grafos disco unitário - grafo de interseção
de círculos de raio 1 no plano.
- ...
ISGCI - Intersection
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
e as referências utilizadas.
Cópia impressa e eletrônica das referências usadas podem ser solicitadas.
Prazo: primeira versão monografia (que já deve estar completa): 26 de novembro.
Segunda versão monografia: 21 de dezembro
Prazo: prévia da versão slides (só de quem não vai entregar monografia): 10 de dezembro.
versão slides: no dia do seminário.
Criada em 23 ago 2005 e atualizada em 27 out e 5 nov 2015 por Márcia R. Cerioli