Problemas topológicos e estruturais em teoria dos grafos.

• Processo: 12/24597-3
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de julho de 2013
• Data de Término da vigência: 31 de dezembro de 2015
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cristina Gomes Fernandes
• Beneficiário: César Israel Hernández Vélez
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Algoritmos de aproximação Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | algoritmos de planaridade | circuitos e caminhos não-separadores | Crossing number | menores de grafos | Teoria dos Grafos

Resumo

Este projeto contempla problemas de natureza topológica ou estrutural em teoria dos grafos. Estamos especialmente interessados em problemas relacionados a planaridade, a menores de grafos, e temas relacionados.Um dos tópicos em que temos interesse é o projeto de um novo algoritmo linear para reconhecer grafos livres de menores de K_5, inspirado no método de planaridade proposto por Lempel, Even, e Cederbaum, que seja mais simples que o algoritmo de Li e Reed. Um segundo tópico envolve o problema de determinar o número mínimo de cruzamentos de arestas em um desenho de um grafo no plano, que é um problema NP-difícil, mesmo quando o grafo dado é cúbico. Nenhum algoritmo de aproximação com razão constante é conhecido para este problema, mesmo para grafos com grau máximo limitado. Há resultados nesta linha apenas sob certas condições topológicas sobre o grafo. Estamos interessados em resultados de aproximação para este problema e problemas correlatos. Existem ainda outros problemas relacionados ao conceito de número de cruzamentos em que temos interesse, como por exemplo a caracterização de grafos cruzamento-críticos. Um outro problema que pretendemos investigar está relacionado a uma conjectura de Lovász, e a um resultado relacionado de Tutte, que mostrou que, em um grafo 3-conexo, para toda aresta, existe um circuito não-separador contendo esta aresta. Tutte mostrou também que, se G é 3-conexo, então o espaço dos ciclos de G é gerado por circuitos induzidos não-separadores de G. Szigeti levantou a seguinte questão relacionada ao resultado de Tutte: em um grafo 3-conexo G, existe uma árvore geradora T tal que todo caminho em T é não-separador em G? Pretendemos trabalhar nesta questão e em outras relacionadas à conjectura de Lovász em questão.O objetivo deste projeto é a obtenção de resultados em problemas como os acima citados, ou outros de natureza semelhante.

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)

FERNANDES, CRISTINA G.; HERNANDEZ-VELEZ, CESAR; DE PINA, JOSE C.; ALFONSIN, JORGE LUIS RAMIREZ. Counting Hamiltonian Cycles in the Matroid Basis Graph. GRAPHS AND COMBINATORICS, v. 35, n. 2, p. 539-550, MAR 2019. (13/03447-6, 12/24597-3, 15/10323-7)

FERNANDES, CRISTINA G.; HERNANDEZ-VELEZ, CESAR; LEE, ORLANDO; DE PINA, JOSE C.. Spanning trees with nonseparating paths. DISCRETE MATHEMATICS, v. 339, n. 1, p. 365-374, JAN 6 2016. (12/24597-3)

HERNANDEZ-VELEZ, CESAR; MEDINA, CAROLINA; SALAZAR, GELASIO. The optimal drawings of K-5,K-n. ELECTRONIC JOURNAL OF COMBINATORICS, v. 21, n. 4, OCT 2 2014. (12/24597-3)