Grant: Discovery Grants Program - Individual
University of Manitoba
$12,000.00
Computational graph theory and geometry
FY 2014-15
Summary
The proposed reearch program involves four main areas of research,1) the graph reconstruction problem; 2) graph embedding algorithms for the torus and other surfaces; 3) finite projective planes; and 4) the 3-hypergraph degree sequence problem. Algorithms which I have developed usually become part of my software package Groups & Graphs. This is a software research tool for graphs, digraphs, combinatorial structures, and their automorphism groups. It is used by researchers world-wide. Item (1) is a major unsolved problem in graph theory. The reconstruction conjecture states that every graph with at least 3 vertices is determined by its subgraphs. To date the solution is unknown. Together with Pierre Ille of the University of Marseille, we have developed some new techniques which seem promising. Item (2) deals with graphs drawn in the torus and other surfaces. The torus is often modelled as the surface of a doughnut or inner tube. The intent is to find an efficient algorithm for finding an embedding of a graph, and to construct a drawing of it. An example would be drawing an electric circuit on an inner tube. This is partly solved for the torus, but is not well understood. Item (3) is concerned with techniques for investigating the existence and enumeration of finite projective planes. Item (4) is a long outstanding unsolved problem, to characterize the integer sequences that are degree sequences of simple 3-hypergraphs. There is a strong likelihood that the problem is NP-complete. If this is the case, this would mean that an efficient algorithm does not exist, which would need to be proved. This is joint work with Pak-Ching Li of the University of Manitoba.
Program
Discovery Grants Program - Individual
Recipient
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
905-2008
Name nom
Kocay, William
Department département
Computer Science
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2008
Award amount
12000
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
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
5
Nb partie
5
Application title
Computational graph theory and geometry
Keyword
NSERC
Application summary
The proposed reearch program involves four main areas of research,1) the graph reconstruction problem; 2) graph embedding algorithms for the torus and other surfaces; 3) finite projective planes; and 4) the 3-hypergraph degree sequence problem. Algorithms which I have developed usually become part of my software package Groups & Graphs. This is a software research tool for graphs, digraphs, combinatorial structures, and their automorphism groups. It is used by researchers world-wide. Item (1) is a major unsolved problem in graph theory. The reconstruction conjecture states that every graph with at least 3 vertices is determined by its subgraphs. To date the solution is unknown. Together with Pierre Ille of the University of Marseille, we have developed some new techniques which seem promising. Item (2) deals with graphs drawn in the torus and other surfaces. The torus is often modelled as the surface of a doughnut or inner tube. The intent is to find an efficient algorithm for finding an embedding of a graph, and to construct a drawing of it. An example would be drawing an electric circuit on an inner tube. This is partly solved for the torus, but is not well understood. Item (3) is concerned with techniques for investigating the existence and enumeration of finite projective planes. Item (4) is a long outstanding unsolved problem, to characterize the integer sequences that are degree sequences of simple 3-hypergraphs. There is a strong likelihood that the problem is NP-complete. If this is the case, this would mean that an efficient algorithm does not exist, which would need to be proved. This is joint work with Pak-Ching Li of the University of Manitoba.