Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Victoria

$32,000.00

Difficult Combinatorial Search Problems and Graph Theory Models and Algorithms for Carbon Frameworks

FY 2020-21

Summary
Theme 1. Difficult Combinatorial Search Problems The graph coloring problem takes as input a graph G and the aim is to color the vertices of G so that adjacent vertices are different colors. This problem is so hard that there are some reasonably small graphs such that finding an optimal coloring is either overly time consuming or not feasible using existing algorithms. One goal of my research is to find faster graph coloring algorithms. The graph coloring problem has many applications including determination of conflict-free schedules, map coloring, and register allocation. Venn diagrams give pictorial representations of all possible logical relations between a finite collection of sets. We plan to exhaustively generate new classes of Venn diagrams. The computational results can be used to investigate conjectures about Venn diagrams. One example of an open question is Winkler's conjecture that any simple Venn diagram can be extended to a larger simple Venn diagram with the addition of a single curve. An (r, g)-cage is a graph having a minimum number of vertices such that each vertex has degree r and the minimum cycle size is g. Cages have attracted a lot of interest from the graph theory community and have properties that make them appealing for a network topology. There are many values for r and g where there is a large gap between the lower bounds given for an (r,g)-cage and the upper bound coming from the number of vertices in a smallest known existing r-regular graph of girth g. Our intent is to try to close those gaps. Theme 2. Graph Theory Models and Algorithms for Carbon Frameworks Graphs are often used by chemists as models for molecules. The molecules considered in this research have carbon frameworks. Fullerenes correspond to 3-regular planar graphs with face sizes 5 or 6. Although fullerenes were only recently discovered (1985) they have been the subject of intense research because of their unique chemistry and potential application in materials science, electronics, nanotechnology and medicine. Benzenoids are unsaturated molecules composed of fused hexagonal rings. More generally, polycyclic aromatic hydrocarbons (PAH's) have mixtures of ring sizes 4, 5, 6 and 7. They occur naturally and as atmospheric pollutants from burning fuels, and can be carcinogenic. The goal of this research is to better understand properties of these molecules such as currents, stability, geometry, and resonance energy. Understanding induced currents is critical for interpreting chemical characterisation by Nuclear Magnetic Resonance. Graph theory models for current represent current by giving a direction and magnitude to each edge of the molecular graph. Graph theory models for currents can be easier to implement and give a simpler representation of the answer than some other numerical approaches. They facilitate prediction of currents for infinite families of molecules. One of our goals is to compare current models to each other looking for inconsistencies and anomalies. The next step is to refine or redevelop the graph theory based methods so that they more accurately reflect the current. The graph theoretic approaches published so far are better suited to benzenoids which are often fairly flat. We plan to develop extensions for predicting current in 3D structures such as fullerenes, or cases where the graph has no perfect matchings or where the cycle sizes vary as for PAH's. Further research will involve determining correlations between computed graph invariants and chosen molecular properties. Definition of new invariants is all too easy, but we will identify those that are efficiently computable and offer information content related to geometry and energy of molecular and extended carbon frameworks
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-05864
Name nom
Myrvold, Wendy
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2014
Award amount
32000
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
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
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
Difficult Combinatorial Search Problems and Graph Theory Models and Algorithms for Carbon Frameworks
Keyword
NSERC
Application summary
Theme 1. Difficult Combinatorial Search Problems The graph coloring problem takes as input a graph G and the aim is to color the vertices of G so that adjacent vertices are different colors. This problem is so hard that there are some reasonably small graphs such that finding an optimal coloring is either overly time consuming or not feasible using existing algorithms. One goal of my research is to find faster graph coloring algorithms. The graph coloring problem has many applications including determination of conflict-free schedules, map coloring, and register allocation. Venn diagrams give pictorial representations of all possible logical relations between a finite collection of sets. We plan to exhaustively generate new classes of Venn diagrams. The computational results can be used to investigate conjectures about Venn diagrams. One example of an open question is Winkler's conjecture that any simple Venn diagram can be extended to a larger simple Venn diagram with the addition of a single curve. An (r, g)-cage is a graph having a minimum number of vertices such that each vertex has degree r and the minimum cycle size is g. Cages have attracted a lot of interest from the graph theory community and have properties that make them appealing for a network topology. There are many values for r and g where there is a large gap between the lower bounds given for an (r,g)-cage and the upper bound coming from the number of vertices in a smallest known existing r-regular graph of girth g. Our intent is to try to close those gaps. Theme 2. Graph Theory Models and Algorithms for Carbon Frameworks Graphs are often used by chemists as models for molecules. The molecules considered in this research have carbon frameworks. Fullerenes correspond to 3-regular planar graphs with face sizes 5 or 6. Although fullerenes were only recently discovered (1985) they have been the subject of intense research because of their unique chemistry and potential application in materials science, electronics, nanotechnology and medicine. Benzenoids are unsaturated molecules composed of fused hexagonal rings. More generally, polycyclic aromatic hydrocarbons (PAH's) have mixtures of ring sizes 4, 5, 6 and 7. They occur naturally and as atmospheric pollutants from burning fuels, and can be carcinogenic. The goal of this research is to better understand properties of these molecules such as currents, stability, geometry, and resonance energy. Understanding induced currents is critical for interpreting chemical characterisation by Nuclear Magnetic Resonance. Graph theory models for current represent current by giving a direction and magnitude to each edge of the molecular graph. Graph theory models for currents can be easier to implement and give a simpler representation of the answer than some other numerical approaches. They facilitate prediction of currents for infinite families of molecules. One of our goals is to compare current models to each other looking for inconsistencies and anomalies. The next step is to refine or redevelop the graph theory based methods so that they more accurately reflect the current. The graph theoretic approaches published so far are better suited to benzenoids which are often fairly flat. We plan to develop extensions for predicting current in 3D structures such as fullerenes, or cases where the graph has no perfect matchings or where the cycle sizes vary as for PAH's. Further research will involve determining correlations between computed graph invariants and chosen molecular properties. Definition of new invariants is all too easy, but we will identify those that are efficiently computable and offer information content related to geometry and energy of molecular and extended carbon frameworks