Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Ottawa

$46,000.00

Foundations and applications of geometric graph theory

FY 2017-18

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
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2016-04936
Name nom
Dujmovic, Vida
Department département
Electrical Engineering and Computer Science , School of - science informatique e
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
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
Partie
2
Nb partie
5
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