Defesa de Doutorado de André Carvalho Silva

Título do Trabalho
Graphs with few crossings and the crossing number of the Kp,q in topological surfaces
Candidato(a)
André Carvalho Silva
Nível
Doutorado
Data
Add to Calender 2018-07-16 00:00:00 2018-07-16 00:00:00 Defesa de Doutorado de André Carvalho Silva Graphs with few crossings and the crossing number of the Kp,q in topological surfaces Sala 85 IC 2 INSTITUTO DE COMPUTAÇÃO mauroesc@ic.unicamp.br America/Sao_Paulo public
Horário
14h00
Local
Sala 85 IC 2
Orientador(a)
Orlando Lee
Banca Examinadora

Condição

Titulares  - Professores Doutores

Unidade/Instituição

Presidente

Orlando Lee

IC/UNICAMP

Membro

Cristiane Maria Sato

CMCC/UFABC

Guilherme Oliveira Mota

CMCC/UFABC

Membro

Candida Nunes da Silva

DC/UFSCar

Jorge Stolfi

IC/UNICAMP

 

Condição

Suplentes  - Professores Doutores

Unidade/Instituição

Suplente

Flávio Keidi Miyazawa

IC/UNICAMP

João Meidanis

IC/UNICAMP

Suplente

José Coelho de Pina Junior

IME/USP

Resumo

Esta tese aborda dois problemas distintos: caracterização de grafos com número de cruzamentos igual a um e determinação do número de cruzamentos do K p,q em superfícies topológicas.

Para grafos com número de cruzamentos um, apresentamos uma completa caracterização estrutural. Também desenvolvemos um algoritmo “prático” para reconhecer estes grafos.

Em relação ao número de cruzamentos do K p,q em superfícies, mostramos que para um inteiro positivo p e uma superfície Σ fixos, existe um conjunto finito D(p, Σ) de desenhos “bons” de grafos bipartido completos K p,r (possivelmente variando o r) tal que, para todo inteiro q e todo desenho D de K p,q , existe um desenho bom D' de K p,q obtido através de duplicação de vértices de um desenho D''  em D(p, Σ) tal que o número de cruzamentos de D' é menor ou igual ao número de cruzamentos de D. Em particular, para todo q suficientemente grande, existe algum desenho do K p,q com o menor número de cruzamentos possível que é obtido a partir de algum desenho de D(p, Σ) através da duplicação de vértices do mesmo. Esse resultado é uma extensão de outro obtido por Cristian et. al. para esfera.