Topological and structural problems in graph theory.

• Grant number: 12/24597-3
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: July 01, 2013
• End date: December 31, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cristina Gomes Fernandes
• Grantee: César Israel Hernández Vélez
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

This project addresses problems of topological or structural nature in graph theory. We are particularly interested in problems related to planarity, graph minors, and related concepts.One of the topics we have interest is the project of a new linear-time algorithm to recognize K_5-minor free graphs, inspired on the planarity method of Lempel, Even, and Cederbaum. Our goal is to propose an algorithm for this task that is simpler than the one of Li and Reed. A second topic involves the problem of determining the crossing number of a given graph, which is a well-known NP-hard problem, even for cubic graphs. No approximation algorithm is known for this problem even for graphs of bounded maximum degree. There are some results in these lines only for graphs that satisfy some topological conditions. We are interested in obtaining approximation results for this and related problems. Also, there are some other problems related to crossing number in which we are interested, such as the characterization of crossing-critical graphs. Another problem we intend to investigate is related to a conjecture of Lovász, and to a result by Tutte that showed that, in every 3-connected graph, for every edge, there exists a non-separating circuit containing this edge. Tutte showed that, if G is a 3-connected graph, then the cycle space of G is generated by induced non-separating circuits of G. Szigeti raised the following question related to Tutte's result: in a 3-connected graph, is there a spanning tree T such that every path in T is non-separating in G? We intend to investigate this and other questions related to this particular conjecture of Lovász.The goal of this project is to obtain results in problems as the ones cited above, and others of similar nature.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

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)

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)