Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$96,000.00

Algorithms in topological graph theory

FY 2024-25

Summary
The research project continues my broad research program across areas. The main research goals are the following: 1. Topological and structural graph theory with algorithmic goals, including approximation algorithms and inapproximability results. One of the main goals here is my long-term project to obtain approximation algorithms for the graph genus problem. Previously, we obtained EPTAS for the case of dense graphs using regularity partitions (FOCS 2018). For sparse case, I have conjectured that the problem is APX-hard, but approximable within a constant factor. Both of these conjectures are widely open and we plan to resolve them. 2. Coloring graphs on surfaces. The known proofs of the famous 4-color theorem are inadequate in the sense that they are "not humanly checkable", algorithmic consequences yield a quadratic-time algorithm that cannot be improved essentially, and does not say anything about 4-coloring of graphs in surfaces of higher genus. Our preliminary discoveries show that all these subtleties may be resolved by a new approach that I developed jointly with K. Kawarabayashi, M. Thorup and C. Thomassen. We aim for a powerful general result, whose consequences would be a near-linear (maybe even linear-time) algorithm for 4-coloring planar graphs and the resolution of Albertson's conjecture from 1981 that graphs on any fixed surface can be 4-colored with exception of a small number of vertices. We also hope to resolve the dual version of the 4-color theorem (the famous Tutte's 4-Flow-Conjecture from 1960s) and its extension (Grotzsch Conjecture). 3. "Square-root'' conjectures. My recent revelation is that three specific conjectures may be tightly related to each other, although they look entirely different. Two of these are the Meyniel conjecture from 1985 that the cop number of any n-vertex graph is O(sqrt(n)), and my conjecture from 2012 that the cop number of any graph of genus g is O(sqrt(g)). The third conjecture is a 1986 conjecture of Colin de Verdiere that \mu(G) = O(sqrt(g)), where \mu(G) is the famous invariant of Colin de Verdiere. 4. Random embeddings of graphs and the genus polynomial. Here I will try to resolve the log-concavity conjecture of Gross, Robbins, and Tucker (1989) and secondly, strengthen my current breakthrough results about the average genus by proving that the number of faces in a random 2-cell embedding is close to Poisson distribution. 5. Twin-width and eigenvalues of graphs.  I will investigate the new notion of the twin-width and its relation to the eigenvalues of graphs. The common theme of all these areas is topological and structural graph theory and algorithmic questions in these areas.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2024-06052
Name nom
Mohar, Bojan
Department département
Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
96000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Algorithms in topological graph theory
Keywords
graphs on surfaces; graph coloring algorithms; structural graph theory; approximation algorithms; cops and robber game; twin-width of graphs; crossing number
Application summary
The research project continues my broad research program across areas. The main research goals are the following: 1. Topological and structural graph theory with algorithmic goals, including approximation algorithms and inapproximability results. One of the main goals here is my long-term project to obtain approximation algorithms for the graph genus problem. Previously, we obtained EPTAS for the case of dense graphs using regularity partitions (FOCS 2018). For sparse case, I have conjectured that the problem is APX-hard, but approximable within a constant factor. Both of these conjectures are widely open and we plan to resolve them. 2. Coloring graphs on surfaces. The known proofs of the famous 4-color theorem are inadequate in the sense that they are "not humanly checkable", algorithmic consequences yield a quadratic-time algorithm that cannot be improved essentially, and does not say anything about 4-coloring of graphs in surfaces of higher genus. Our preliminary discoveries show that all these subtleties may be resolved by a new approach that I developed jointly with K. Kawarabayashi, M. Thorup and C. Thomassen. We aim for a powerful general result, whose consequences would be a near-linear (maybe even linear-time) algorithm for 4-coloring planar graphs and the resolution of Albertson's conjecture from 1981 that graphs on any fixed surface can be 4-colored with exception of a small number of vertices. We also hope to resolve the dual version of the 4-color theorem (the famous Tutte's 4-Flow-Conjecture from 1960s) and its extension (Grotzsch Conjecture). 3. "Square-root'' conjectures. My recent revelation is that three specific conjectures may be tightly related to each other, although they look entirely different. Two of these are the Meyniel conjecture from 1985 that the cop number of any n-vertex graph is O(sqrt(n)), and my conjecture from 2012 that the cop number of any graph of genus g is O(sqrt(g)). The third conjecture is a 1986 conjecture of Colin de Verdiere that \mu(G) = O(sqrt(g)), where \mu(G) is the famous invariant of Colin de Verdiere. 4. Random embeddings of graphs and the genus polynomial. Here I will try to resolve the log-concavity conjecture of Gross, Robbins, and Tucker (1989) and secondly, strengthen my current breakthrough results about the average genus by proving that the number of faces in a random 2-cell embedding is close to Poisson distribution. 5. Twin-width and eigenvalues of graphs.  I will investigate the new notion of the twin-width and its relation to the eigenvalues of graphs. The common theme of all these areas is topological and structural graph theory and algorithmic questions in these areas.