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

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

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)

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)