Grant: Discovery Grants Program - Individual
The University of British Columbia
$29,000.00
Uncertainty in Geometric Graphs
EF 2024-25
Résumé
The proposed research focuses on graphs that are defined by geometric relationships between entities, such as the distance between mobile agents. It is often the case that the location of these entities is not precisely known and, as in the case of mobile agents, can change over time. This uncertainty permits the possibility of relationships between entities that may not truly exist. In the case of communication networks, where the relationship represents the ability to send a direct message, agents waste resources trying to send messages to agents that are now beyond their communication distance. Suppose that the true location of a single agent may be obtained and broadcast to all agents every second, how would this single location be chosen to avoid wasted messages?
This scenario may be modelled as a geometric graph. Assuming that each mobile agent has the same maximum speed and can move in any direction in 2D space, the agent's current location lies anywhere in a disk whose centre is the agent's last known location and whose radius is its speed multiplied by the time since its location was obtained. If two such disks (expanded by half the common communication distance) intersect, the corresponding agents may be able to exchange direct messages. If we consider the graph whose vertices are the agents and whose edges connect agents whose disks intersect, the maximum degree of this graph is the maximum number of direct messages any agent needs to send to reach all its possible recipients. Finding the true location of an agent modifies this intersection graph by decreasing the size of that agent's disk. Meanwhile, all other disks grow since the possible locations of these other agents increases.
I propose to study algorithms for deciding how to choose which geometric entities to query to obtain more precise information about their uncertainty regions (e.g. the disks in the previous example) with an overall goal of optimizing an associated geometric graph (e.g. intersection graph) property, like maximum degree, chromatic number, maximum clique size, etc. The fact that queries are costly, either in the time required to make the query or in the number of bits of information obtained, makes the choice of what to query at each step challenging.
Our perspective of geometric uncertainty is useful as a way to evaluate geometric representations of graphs as well. A drawing of a graph using geometric objects may be preferable to another if it allows larger perturbations or uncertainty in the location of the vertex objects while preserving the graph it represents. For example, a rectangle visibility representation of a graph may be more difficult to interpret if relatively small increases in the rectangles change the graph.
The research involves aspects of graph theory, graph representation, uncertain inputs, uncertainty due to motion, tolerance of geometric configurations, and even distributed algorithms.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2022-04449
Name nom
Evans, William
Department département
Computer Science
Organization id
2
Institution établissement
The University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2022
Award amount
29000
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Uncertainty in Geometric Graphs
Keywords
geometric graph representation; uncertain or imprecise inputs; intersection graphs; visibility graphs; uncertainty over time
Application summary
The proposed research focuses on graphs that are defined by geometric relationships between entities, such as the distance between mobile agents. It is often the case that the location of these entities is not precisely known and, as in the case of mobile agents, can change over time. This uncertainty permits the possibility of relationships between entities that may not truly exist. In the case of communication networks, where the relationship represents the ability to send a direct message, agents waste resources trying to send messages to agents that are now beyond their communication distance. Suppose that the true location of a single agent may be obtained and broadcast to all agents every second, how would this single location be chosen to avoid wasted messages?
This scenario may be modelled as a geometric graph. Assuming that each mobile agent has the same maximum speed and can move in any direction in 2D space, the agent's current location lies anywhere in a disk whose centre is the agent's last known location and whose radius is its speed multiplied by the time since its location was obtained. If two such disks (expanded by half the common communication distance) intersect, the corresponding agents may be able to exchange direct messages. If we consider the graph whose vertices are the agents and whose edges connect agents whose disks intersect, the maximum degree of this graph is the maximum number of direct messages any agent needs to send to reach all its possible recipients. Finding the true location of an agent modifies this intersection graph by decreasing the size of that agent's disk. Meanwhile, all other disks grow since the possible locations of these other agents increases.
I propose to study algorithms for deciding how to choose which geometric entities to query to obtain more precise information about their uncertainty regions (e.g. the disks in the previous example) with an overall goal of optimizing an associated geometric graph (e.g. intersection graph) property, like maximum degree, chromatic number, maximum clique size, etc. The fact that queries are costly, either in the time required to make the query or in the number of bits of information obtained, makes the choice of what to query at each step challenging.
Our perspective of geometric uncertainty is useful as a way to evaluate geometric representations of graphs as well. A drawing of a graph using geometric objects may be preferable to another if it allows larger perturbations or uncertainty in the location of the vertex objects while preserving the graph it represents. For example, a rectangle visibility representation of a graph may be more difficult to interpret if relatively small increases in the rectangles change the graph.
The research involves aspects of graph theory, graph representation, uncertain inputs, uncertainty due to motion, tolerance of geometric configurations, and even distributed algorithms.