Grant: Discovery Grants Program - Individual
University of Waterloo
$21,000.00
Crossing Numbers of Graphs, List Colourings of Graphs, Flows in Graphs
FY 2020-21
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?
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-04156
Name nom
Richter, Bruce
Department département
Combinatorics & 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
2020
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 grants programs
Group fr
Programmes de subventions à 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
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Installment
inst:2-5
Partie
4
Nb partie
5
Application title
Crossing Numbers of Graphs, List Colourings of Graphs, Flows in Graphs
Keyword
NSERC
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?