Grant: Discovery Grants Program - Individual
University of Victoria
$30,000.00
Finding torus obstructions/graph theory and algorithms for chemistry
FY 2009-10
Summary
Project 1: Finding the Torus Obstructions- A torus is a surface shaped like a doughnut. A topological obstruction for the torus is a graph G with minimum degree three that is not embeddable on the torus but for all edges e, G-e embeds on the torus. A minor order obstruction has the additional property that for all edges e, G contract e embeds on the torus. To date, we have found 249,227 topological obstructions and 17,354 minor order obstructions. The aims of our future research are to check the previous results using independent computations, to develop better computational tools so that the search can be extended, to search for patterns in the known obstructions so that they can expressed more succinctly, to generate and prove conjectures regarding the complete set of obstructions, and to use the insights gained for developing practical algorithms for torus embedding.
Project 2: Graph Algorithms for Fullerene Chemistry- Fullerenes are all-carbon molecules whose structures correspond to 3-regular planar graphs with face sizes five or six. This discrete molecular form of carbon was unknown before 1985, but now fullerenes and their relatives the carbon nanotubes have a chemistry and physics that is described in thousands of papers in the literature, with potential applications from materials science to medicine all being driven by their unusual combination of properties. There are various graph theoretical properties which are of direct interest to chemists. Working in collaboration with a theoretical chemist, a system called FuiGui (Fullerene Interactive Graphical User Interface) has been developed to faciliate research on the graphs which represent fullerenes. The goals of this research are to continue development of the FuiGui research tool and to apply it to provide further insight to fullerene chemistry.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
41927-2009
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
2009
Competition year année de concours
2009
Award amount
30000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
1
Nb partie
5
Application title
Finding torus obstructions/graph theory and algorithms for chemistry
Keyword
NA
Application summary
Project 1: Finding the Torus Obstructions- A torus is a surface shaped like a doughnut. A topological obstruction for the torus is a graph G with minimum degree three that is not embeddable on the torus but for all edges e, G-e embeds on the torus. A minor order obstruction has the additional property that for all edges e, G contract e embeds on the torus. To date, we have found 249,227 topological obstructions and 17,354 minor order obstructions. The aims of our future research are to check the previous results using independent computations, to develop better computational tools so that the search can be extended, to search for patterns in the known obstructions so that they can expressed more succinctly, to generate and prove conjectures regarding the complete set of obstructions, and to use the insights gained for developing practical algorithms for torus embedding.
Project 2: Graph Algorithms for Fullerene Chemistry- Fullerenes are all-carbon molecules whose structures correspond to 3-regular planar graphs with face sizes five or six. This discrete molecular form of carbon was unknown before 1985, but now fullerenes and their relatives the carbon nanotubes have a chemistry and physics that is described in thousands of papers in the literature, with potential applications from materials science to medicine all being driven by their unusual combination of properties. There are various graph theoretical properties which are of direct interest to chemists. Working in collaboration with a theoretical chemist, a system called FuiGui (Fullerene Interactive Graphical User Interface) has been developed to faciliate research on the graphs which represent fullerenes. The goals of this research are to continue development of the FuiGui research tool and to apply it to provide further insight to fullerene chemistry.