Detalhes do Documento

Descrição

Orientador: Orlando Lee

Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo: O número de cruzamentos de um grafo G em uma superfície ? é o menor número de cruzamentos de arestas dentre todos os possíveis desenhos de G em ?. Esta tese aborda dois problemas distintos envolvendo número de cruzamentos de grafos: caracterização de grafos com número de cruzamentos igual a um e determinação do número de cruzamentos do Kp,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 Kp,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 bipartidos completos Kp,r (possivelmente variando o r) tal que, para todo inteiro q e todo desenho D de Kp,q, existe um desenho bom D' de Kp,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 Kp,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

Abstract: The crossing number of a graph G in a surface ? is the least amount of edge crossings among all possible drawings of G in ?. This thesis deals with two problems on crossing number of graphs: characterization of graphs with crossing number one and determining the crossing number of Kp,q in topological surfaces. For graphs with crossing number one, we present a complete structural characterization. We also show a "practical" algorithm for recognition of such graphs. For the crossing number of Kp,q in surfaces, we show that for a fixed positive integer p and a fixed surface ?, there is a finite set D(p,?) of good drawings of complete bipartite graphs Kp,r (with distinct values of r) such that, for every positive integer q and every good drawing D of Kp,q, there is a good drawing D' of Kp,q obtained from a drawing D'' of D(p,?) by duplicating vertices of D'' and such that the crossing number of D' is at most the crossing number of D. In particular, for any large enough q, there exists some drawing of Kp,q with fewest crossings which can be obtained from a drawing of D(p,?) by duplicating vertices. This extends a result of Christian et. al. for the sphere

Doutorado

Ciência da Computação

Doutor em Ciência da Computação

FAPESP

2014/14375-9