Número de Cruzamentos de um Grafo

• Processo: 14/14375-9
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de fevereiro de 2015
• Data de Término da vigência: 15 de março de 2018
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Orlando Lee
• Beneficiário: André Carvalho Silva
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Bolsa(s) vinculada(s): 15/04385-0 - Número de cruzamentos de grafos em superfícies arbitrárias, BE.EP.DR
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: desenhos de grafos | genus de um grafo | número de cruzamentos | Teoria dos Grafos

Resumo

O número de cruzamentos de um grafo G é o menor número de cruzamentos entre arestas dentre todos os desenhos de G. Um grafo é dito planar quando existe um desenho no plano do mesmo que não contém cruzamentos. Desta forma, o número de cruzamentos de um grafo pode ser entendido como uma medida de não-planaridade de um grafo.Achar um desenho ótimo com relação ao número de cruzamentos de um grafo tem aplicações em VLSI (Very Large Scale Integration) e na área de graph drawing.Neste projeto trataremos de duas importantes conjecturas na área de número de cruzamentos de um grafo: as conjecturas de Zarankiewicz e Hill. Estas conjecturas descrevem uma fórmula fechada para determinar o número de cruzamentos dos grafos bipartido completo e completo, respectivamente.

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

SILVA, ANDRE C.; ARROYO, ALAN; RICHTER, R. BRUCE; LEE, ORLANDO. Graphs with at most one crossing. DISCRETE MATHEMATICS, v. 342, n. 11, p. 3201-3207, NOV 2019. (14/14375-9, 15/04385-0, 15/11937-9)

RICHTER, R. BRUCE; SILVA, ANDRE C.; LEE, ORLANDO. Bounding the Number of Non-duplicates of the q-Side in Simple Drawings of K-p,K-q. GRAPHS AND COMBINATORICS, AUG 2021. (15/11937-9, 15/04385-0, 14/14375-9)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SILVA, André Carvalho. Graphs with few crossings and the crossing number of Kp,q in topological surfaces. 2018. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.