Grant: Discovery Grants Program - Individual

Graphs are the most general model for computer and communication networks, roads, waterways, and anygeneral infrastructure. Naturally many optimization problems arise. For example, what is the most efficientroute for a packet through the Internet, or for a shipment between two locations. The efficiency itself can bemeasured in terms of time, cost, number of intermediary nodes used, etc. The underlying problem in all suchcases is an optimization problem on graphs. We study optimization problems on graphs. The goal of thisresearch is to develop efficient algorithmic techniques, and data structures that allow efficient solutions for theproblems considered. We concentrate on geometric graphs, i.e. graphs that have certain structure derived fromor related to the geometric spaces. These are graphs embedded in metric spaces, graphs with a metric imposedon their edges, or graphs whose edges have certain geometric properties. For example, the RelativeNeighbourhood Graph (RNG) of a set of points has applications to wireless routing, clustering, etc. One of themost commonly used and studied geometric graphs are the triangulations. They are applied to geographicinformation systems (including GPS), computer graphics and visualization, medical imaging andcomputer-guided surgery, meshing and modeling, just to mention a few. Every application requirestriangulations with certain quality and properties. It is also very important that these are efficiently computable,especially in time-sensitive applications. Thus, our ability to perform certain tasks quickly and efficiently reliesupon efficient algorithms for constructing optimal triangulations. Finally, it is very important to study thegeneral properties of geometric graphs in order to advance our conceptual understanding of the computationalparadigms.