Foundations and applications of geometric graph theory

几何图论基础与应用

• 批准号: RGPIN-2016-04936
• 负责人: Dujmovic, Vida
• 金额: $ 3.35万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=649734
• 关键词: Foundations; applications; 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**

图和网络被用来对来自经济、工程、社会科学、遗传学、数学和计算机科学等许多领域的结构信息进行建模。可视化是帮助人类理解信息的关键工具之一。许多现实世界的应用程序要求以一种易于阅读和理解的方式可视化图形，或者以满足某些物理约束的方式进行布局。在大规模网络激增的今天，这一点尤其正确。生成此类网络的布局提出了许多具有挑战性的算法和组合问题。要在这些问题上取得进展，不仅需要对几何的深入理解，还需要结构图论方面的深刻理论成果。这个项目的核心是发现图形(它们的拓扑和结构)与几何之间的丰富联系，并将它们应用于：关于图形可视化(如二维和三维图形绘制)的基本问题；图形在曲面上的嵌入；几何图论；以及几何与图论相结合的其他应用程序，如几何扳手。最后，还将使用结构工具以及Moser和Tardos的熵压缩方法来研究各种图着色问题**