Busca avançada
Ano de início
Entree

Problemas topológicos e estruturais em teoria dos grafos

Processo: 12/24597-3
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de julho de 2013
Vigência (Término): 31 de dezembro de 2015
Área do 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

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. Citações Web of Science: 0.
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. Citações Web of Science: 0.
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. Citações Web of Science: 2.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.