Advanced search
Start date
Betweenand
Related content

The Crossing Number of Graphs

Grant number: 14/14375-9
Support Opportunities:Scholarships in Brazil - Doctorate
Start date: February 01, 2015
End date: March 15, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Orlando Lee
Grantee:André Carvalho Silva
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated scholarship(s):15/04385-0 - Crossing number of graphs in arbitrary surfaces, BE.EP.DR

Abstract

The crossing number of a graph G is the minimum crossing number of all drawings of G. A graph is planar if its crossing number is zero. Thus the crossing number is a generalization of the concept of planarity of a graph.Crossing number has applications in Very Large Scale Integration and in graph drawing problems.This project will address two important conjecture about the crossing number: Hill's and Zaranckiewicz's. Those conjecture describe formulas for the crossing number for the classes of complete graphs and bipartite complete graphs.

News published in Agência FAPESP Newsletter about the scholarship:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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)
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, . (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, . (15/11937-9, 15/04385-0, 14/14375-9)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
SILVA, André Carvalho. Grafos com poucos cruzamentos e o número de cruzamentos do Kp,q em superfícies topológicas. 2018. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.