Uncertainty in Geometric Graphs

点击翻译按钮获取中文摘要

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.