Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$41,000.00

Algorithms for near-planar graphs

EF 2020-21

Résumé
What do a subway map, an entity-relationship diagram, a social network, a street map, a hierarchical organization, a control flow diagram and a biochemical pathway have in common? They are all examples of structures and relationships that can be modeled as a graph: an abstract structure consisting of vertices (representing sites, nodes, points, . . . ) and edges, i.e., pairs of vertices (representing connections, arcs, streets, implications, . . . ). Typically one wants to know some properties of these structures (“how many different frequencies do radio sites need to avoid interference?”, “how many people all mutually know each other?”, “what is the shortest way to get from A to B?”) which, when translated to the language of graphs, become the well-known optimization problems of coloring, clique and shortest path. One commonly studied subclass of graphs are the planar graphs, which can be drawn in the plane without crossings. They frequently appear in applications: for example graphs (such as Delauney triangulations) that express interactions between geometric sites are often planar. Optimization-problems in planar graphs have been studied intensely for many decades, and many examples are known where optimization problems can be solved more efficiently in planar graphs than in arbitrary graphs. There also exist some general-purpose tools for developing algorithms for planar graphs, such as Baker's approximation scheme, separators and bidimensionality. In real life, graphs arising from applications such as road networks are often close to planar, but do require a few crossings (e.g. where an underpass meets a bridge). In recent years, this has caused much interest in so-called "near-planar graphs"---a catch-all term for any class of graphs that are not necessarily planar, but that are "close" in some way. Prime examples of these are graphs of small genus (i.e., they can be embedded in a surface of small genus), k-planar graphs (i.e., every edge can have at most k crossings) or generalization of geometric graphs (e.g., higher-order Delauney triangulation). The goal of the proposed research is to find better algorithms for optimization problems for such near-planar graphs. Quite a bit is known already for graphs of small genus (and generally, all so-called H-minor free graphs). However, for other near-planar graphs most existing results either focus on properties (“how many edges are there?”) or are trivially obtained by planarizing the graph. Few algorithms are known for optimization problems; I propose to explore such algorithms, with the short-term objective of transferring numerous known results for planar graphs to near-planar graphs, and the long-term vision of establishing general-purpose tools for developing algorithms for near-planar graphs. This topic is ideally suited for HQP training, enabling them to develop the logical thinking and problem-solving skills crucial for their later work in the software industry or academia.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2020-03958
Name nom
Biedl, Therese
Department département
Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2020
Award amount
41000
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:1-5
Partie
5
Nb partie
5
Application title
Algorithms for near-planar graphs
Keyword
NSERC
Application summary
What do a subway map, an entity-relationship diagram, a social network, a street map, a hierarchical organization, a control flow diagram and a biochemical pathway have in common? They are all examples of structures and relationships that can be modeled as a graph: an abstract structure consisting of vertices (representing sites, nodes, points, . . . ) and edges, i.e., pairs of vertices (representing connections, arcs, streets, implications, . . . ). Typically one wants to know some properties of these structures (“how many different frequencies do radio sites need to avoid interference?”, “how many people all mutually know each other?”, “what is the shortest way to get from A to B?”) which, when translated to the language of graphs, become the well-known optimization problems of coloring, clique and shortest path. One commonly studied subclass of graphs are the planar graphs, which can be drawn in the plane without crossings. They frequently appear in applications: for example graphs (such as Delauney triangulations) that express interactions between geometric sites are often planar. Optimization-problems in planar graphs have been studied intensely for many decades, and many examples are known where optimization problems can be solved more efficiently in planar graphs than in arbitrary graphs. There also exist some general-purpose tools for developing algorithms for planar graphs, such as Baker's approximation scheme, separators and bidimensionality. In real life, graphs arising from applications such as road networks are often close to planar, but do require a few crossings (e.g. where an underpass meets a bridge). In recent years, this has caused much interest in so-called "near-planar graphs"---a catch-all term for any class of graphs that are not necessarily planar, but that are "close" in some way. Prime examples of these are graphs of small genus (i.e., they can be embedded in a surface of small genus), k-planar graphs (i.e., every edge can have at most k crossings) or generalization of geometric graphs (e.g., higher-order Delauney triangulation). The goal of the proposed research is to find better algorithms for optimization problems for such near-planar graphs. Quite a bit is known already for graphs of small genus (and generally, all so-called H-minor free graphs). However, for other near-planar graphs most existing results either focus on properties (“how many edges are there?”) or are trivially obtained by planarizing the graph. Few algorithms are known for optimization problems; I propose to explore such algorithms, with the short-term objective of transferring numerous known results for planar graphs to near-planar graphs, and the long-term vision of establishing general-purpose tools for developing algorithms for near-planar graphs. This topic is ideally suited for HQP training, enabling them to develop the logical thinking and problem-solving skills crucial for their later work in the software industry or academia.