Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of British Columbia

$22,000.00

Geometric Representation of Graphs

EF 2019-20

Résumé
This proposal outlines a plan to explore properties of graphs that are defined geometrically. Such graphs arise, for example, in the study of transportation, communication, and sensor networks. The focus of the proposed research is on graphs defined by some notion of contact or visibility between geometric objects. Two objects are mutually visible if there exists a line segment connecting them that does not intersect another object. They are in contact if their boundaries, but not their interiors, intersect. A main theme of the proposed research concerns simultaneous representation, where one set of objects can define more than one graph. By considering contact or visibility between objects in a limited number of directions, we obtain a limited number of different contact or visibility graphs on those objects. My goal is to understand properties of these sets of simultaneously representable graphs and to design algorithms to find such representations.******The most commonly studied example of simultaneous representation is the problem of finding a planar drawing of each of two graphs where each vertex is the same point in both drawings (and edges are curves that connect their endpoints). The problem is important, beyond its theoretical interest, for its application to the visual analysis of a changing network on a common set of vertices. While point/curve simultaneous representation has received a great deal of attention, the study of alternative simultaneous representations has been much more limited. I propose to study simultaneous representation using geometric objects, such as segments, rectangles, and disks, as vertices where visibility or contact determines adjacency. For example, rectangles in the plane define one graph when visibility is vertical and another when visibility is horizontal. What pairs of graphs can be represented in this fashion? Given two graphs, what is the complexity of finding such a representation if it exists? Can the existence of such a representation aid in the solving of problems restricted to these graphs?******The kinds of graphs that can be represented implicitly using visibility changes depending on the type of object and on the notion of visibility. Part of this proposed research considers visibility representations that allow some amount of ""X-ray vision"", that is, two objects are mutually k-visible if there is a segment connecting them that intersects at most k other objects. Such graphs arise, for example, when considering networks of sensors that can penetrate a limited number of walls. The model increases the set of graphs that can be represented beyond traditional 0-visibility representations, but in a way that is limited by the geometry of the representation. An objective of the proposed research is to understand to what extent permitting k-visibility impacts the class of representable graphs and to relate this class to other well-known graph classes.**
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-03856
Name nom
Evans, William
Department département
Computer Science
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2016
Award amount
22000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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:4 - 5
Partie
4
Nb partie
5
Application title
Geometric Representation of Graphs
Keyword
NSERC
Application summary
This proposal outlines a plan to explore properties of graphs that are defined geometrically. Such graphs arise, for example, in the study of transportation, communication, and sensor networks. The focus of the proposed research is on graphs defined by some notion of contact or visibility between geometric objects. Two objects are mutually visible if there exists a line segment connecting them that does not intersect another object. They are in contact if their boundaries, but not their interiors, intersect. A main theme of the proposed research concerns simultaneous representation, where one set of objects can define more than one graph. By considering contact or visibility between objects in a limited number of directions, we obtain a limited number of different contact or visibility graphs on those objects. My goal is to understand properties of these sets of simultaneously representable graphs and to design algorithms to find such representations.******The most commonly studied example of simultaneous representation is the problem of finding a planar drawing of each of two graphs where each vertex is the same point in both drawings (and edges are curves that connect their endpoints). The problem is important, beyond its theoretical interest, for its application to the visual analysis of a changing network on a common set of vertices. While point/curve simultaneous representation has received a great deal of attention, the study of alternative simultaneous representations has been much more limited. I propose to study simultaneous representation using geometric objects, such as segments, rectangles, and disks, as vertices where visibility or contact determines adjacency. For example, rectangles in the plane define one graph when visibility is vertical and another when visibility is horizontal. What pairs of graphs can be represented in this fashion? Given two graphs, what is the complexity of finding such a representation if it exists? Can the existence of such a representation aid in the solving of problems restricted to these graphs?******The kinds of graphs that can be represented implicitly using visibility changes depending on the type of object and on the notion of visibility. Part of this proposed research considers visibility representations that allow some amount of ""X-ray vision"", that is, two objects are mutually k-visible if there is a segment connecting them that intersects at most k other objects. Such graphs arise, for example, when considering networks of sensors that can penetrate a limited number of walls. The model increases the set of graphs that can be represented beyond traditional 0-visibility representations, but in a way that is limited by the geometry of the representation. An objective of the proposed research is to understand to what extent permitting k-visibility impacts the class of representable graphs and to relate this class to other well-known graph classes.**