Grant: Discovery Grants Program - Individual
University of Ottawa
$46,000.00
Foundations and applications of geometric graph theory
EF 2020-21
Résumé
Graphs and Networks are used to model structural information arising from many fields such as economics, engineering, social sciences, genetics, mathematics and computer science. Visualization is one of the key tools that aids humans in understanding information. Many real-world applications require graphs to be visualized in a way that is easy to read and understand, or to be laid out satisfying some physical constraints. This is especially true today with the proliferation of large-scale networks. Producing layouts of such networks presents many challenging algorithmic and combinatorial problems. To make advances on these problems, deep theoretical results in structural graph theory as well as deep understanding of geometry is needed. The core of this project is aimed at discovering rich connections between graphs (their topology and structure) and geometry and applying them to: fundamental problems about graph visualizations (such as graph drawings in two and three dimensions); embeddings of graphs on surfaces; geometric graph theory; and other applications where geometry meets graph theory such as geometric spanners. Finally, various graph colouring problems will also be studied using both structural tools as well as the entropy compression method of Moser and Tardos
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2016-04936
Name nom
Dujmovic, Vida
Department département
School of Electrical Engineering and Computer Science
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2016
Award amount
46000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
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
Installment
inst:5-6
Partie
2
Nb partie
6
Application title
Foundations and applications of geometric graph theory
Keyword
NSERC
Application summary
Graphs and Networks are used to model structural information arising from many fields such as economics, engineering, social sciences, genetics, mathematics and computer science. Visualization is one of the key tools that aids humans in understanding information. Many real-world applications require graphs to be visualized in a way that is easy to read and understand, or to be laid out satisfying some physical constraints. This is especially true today with the proliferation of large-scale networks. Producing layouts of such networks presents many challenging algorithmic and combinatorial problems. To make advances on these problems, deep theoretical results in structural graph theory as well as deep understanding of geometry is needed. The core of this project is aimed at discovering rich connections between graphs (their topology and structure) and geometry and applying them to: fundamental problems about graph visualizations (such as graph drawings in two and three dimensions); embeddings of graphs on surfaces; geometric graph theory; and other applications where geometry meets graph theory such as geometric spanners. Finally, various graph colouring problems will also be studied using both structural tools as well as the entropy compression method of Moser and Tardos