Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$21,000.00

Crossing Numbers of Graphs, List Colourings of Graphs, Flows in Graphs

EF 2023-24

Résumé
How data is presented, especially the relations between the parts of the data set, can help in the analysis of the data. If the data is presented on a page, there may be connections between some of the data points indicating their significance to each other. To make the presentation of the data clear, we might try to minimize the number of these connections that cross each other in the diagram. There is a similar issue in the construction of a computer chip: the connections between the different nodes on the chip should not cross, we do not want a short circuit. Here are two problems  about the general crossing number problem of a network:  1) How can we draw a network in the plane so as to have few pairs of connections that cross each other? 2) What is this minimum number of crossings for this network? One important example is the complete network, in which every pair of nodes is connected. For nearly 60 years, there has been a conjectured value for the minimum number, depending on the number n of nodes in the network. We only know the conjecture is true for n at most 12. Some of my work focusses on finding general properties of a drawing of a complete network that must hold if the drawing is to be one with a minimum number of crossings. With this work, we hope to substantially improve the prospects for verifying the conjecture both for larger values of n, with the ultimate goal being for all n. Our work on complete networks has led to implications for drawings of more general networks. Some natural considerations about how edges cross in a drawing of complete network correspond exactly with geometric considerations like: the drawing can be made in the plane so that every edge is a straight line segment or the drawing can be made in the sphere so that every edge is contained in a great circle. What is interesting is that generalizations of these geometric conditions can describe drawings of general networks, not just complete ones. Thus, we can extend the range of geometric considerations in the study of general networks. In the first of two different directions, we are interested in a network N such that each each node v has a preassigned set L(v) of colours. We wish to colour all the nodes of N such that each vertex v is assigned a colour in L(v) and such that connected nodes receive different colours. This type of problem arose in the assignment of frequencies for radio and television stations, and has many other applications. Thomassen proved that if N is a planar network and each L(v) has at least 5 colours, then there is a colouring as described.   We are interested in extending the validity of Thomassen's Theorem. In particular, what happens if we attach a 5-list-colourable graph H to a face of a planar graph?  There are obstructions to 5-list-colourability; what are they? Can we describe interesting families of graphs H for which the result is always 5-list-colourable?
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2019-04156
Name nom
Richter, Bruce
Department département
Combinatorics and Optimization - Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2019
Award amount
21000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Crossing Numbers of Graphs, List Colourings of Graphs, Flows in Graphs
Keyword
crossing numbers of graphs; flows in graphs; geometric graphs; list colourings of planar graphs
Application summary
How data is presented, especially the relations between the parts of the data set, can help in the analysis of the data. If the data is presented on a page, there may be connections between some of the data points indicating their significance to each other. To make the presentation of the data clear, we might try to minimize the number of these connections that cross each other in the diagram. There is a similar issue in the construction of a computer chip: the connections between the different nodes on the chip should not cross, we do not want a short circuit. Here are two problems  about the general crossing number problem of a network:  1) How can we draw a network in the plane so as to have few pairs of connections that cross each other? 2) What is this minimum number of crossings for this network? One important example is the complete network, in which every pair of nodes is connected. For nearly 60 years, there has been a conjectured value for the minimum number, depending on the number n of nodes in the network. We only know the conjecture is true for n at most 12. Some of my work focusses on finding general properties of a drawing of a complete network that must hold if the drawing is to be one with a minimum number of crossings. With this work, we hope to substantially improve the prospects for verifying the conjecture both for larger values of n, with the ultimate goal being for all n. Our work on complete networks has led to implications for drawings of more general networks. Some natural considerations about how edges cross in a drawing of complete network correspond exactly with geometric considerations like: the drawing can be made in the plane so that every edge is a straight line segment or the drawing can be made in the sphere so that every edge is contained in a great circle. What is interesting is that generalizations of these geometric conditions can describe drawings of general networks, not just complete ones. Thus, we can extend the range of geometric considerations in the study of general networks. In the first of two different directions, we are interested in a network N such that each each node v has a preassigned set L(v) of colours. We wish to colour all the nodes of N such that each vertex v is assigned a colour in L(v) and such that connected nodes receive different colours. This type of problem arose in the assignment of frequencies for radio and television stations, and has many other applications. Thomassen proved that if N is a planar network and each L(v) has at least 5 colours, then there is a colouring as described.   We are interested in extending the validity of Thomassen's Theorem. In particular, what happens if we attach a 5-list-colourable graph H to a face of a planar graph?  There are obstructions to 5-list-colourability; what are they? Can we describe interesting families of graphs H for which the result is always 5-list-colourable?