Foundations and applications of geometric graph theory

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

Graphs and Networks are used to model structural information arising from many fields such as economics, engineering, social sciences, genetics, mathematics and computer science. Visualization is one of the key tools that aids humans in understanding information. Many real-world applications require graphs to be visualized in a way that is easy to read and understand, or to be laid out satisfying some physical constraints. This is especially true today with the proliferation of large-scale networks. Producing layouts of such networks presents many challenging algorithmic and combinatorial problems. To make advances on these problems, deep theoretical results in structural graph theory as well as deep understanding of geometry is needed. The core of this project is aimed at discovering rich connections between graphs (their topology and structure) and geometry and applying them to: fundamental problems about graph visualizations (such as graph drawings in two and three dimensions); embeddings of graphs on surfaces; geometric graph theory; and other applications where geometry meets graph theory such as geometric spanners. Finally, various graph colouring problems will also be studied using both structural tools as well as the entropy compression method of Moser and Tardos**