Crossing number of graphs in arbitrary surfaces

• Grant number: 15/04385-0
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: July 17, 2015
• End date: July 01, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Orlando Lee
• Grantee: André Carvalho Silva
• Supervisor: R. Bruce Richter
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: University of Waterloo, Canada
• Associated to the scholarship: 14/14375-9 - The Crossing Number of Graphs, BP.DR

Abstract

The crossing number of a graph G is the least number of crossings of all the drawings of G in S.A graph is embeddable if we can draw it in S without crossings. In the plane those graphs are denoted planar. Therefore the crossing number of a graph is a generalization of the concept of non-planarity(embeddability).Finding a optimal drawing of a graph has applications in Very Large Scale Integration and in Graph Drawing. (AU)

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, 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)