CAREER: Embedding, Morphing, and Visualizing Dynamic Graphs

职业：嵌入、变形和可视化动态图

• 批准号: 0545743
• 负责人: Stephen Kobourov
• 金额: $ 40.45万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-02-15 至 2011-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0545743&HistoricalAwards=false
• 关键词: CAREER; Embedding; Morphing; Visualizing; Dynamic

The main research goal of this project is to develop practical algorithms for modeling and visualizing dynamic processes based on solid theoretical foundations. Many processes, such as software evolution over time and robot dispersal over a terrain, are naturally modeled with dynamic graphs. While much is known about static graphs, dynamic graphs pose many unsolved challenges, both theoretical and practical. Specifically, the design and implementation of algorithms for modeling and visualizing dynamic graphs can make an impact on graph theory, computational geometry, information visualization, and sensor networks.The central notions in this work are simultaneous graph embedding, graph morphing, and dynamic graphs. Simultaneous graph embedding refers to a common embedding of two or more related graphs. Research on this problem involves studying characterizations of the classes of graphs that allow planar simultaneous embeddings and designing algorithms for testing simultaneous planarity. Graph morphing refers to a transformation of a given source graph into another related target graph. Research on this problem involves designing polynomial time algorithms for morphing in Euclidean and Riemannian spaces and investigating methods for generalizing the notion of barycentric coordinates to non-Euclidean spaces. Visualizing dynamic graphs requires the ability to process large amounts of data in real time while providing informative representations of the underlying data. Research on this problem involves developing effective and efficient algorithms for dynamic graph visualization, as well as applying the new models to mobile sensor localization, robot dispersal, and map building.

该项目的主要研究目标是基于坚实的理论基础开发用于建模和可视化动态过程的实用算法。 许多过程，例如软件随时间的演变和机器人在地形上的分散，都是用动态图自然地建模的。尽管人们对静态图了解很多，但动态图在理论和实践方面都提出了许多未解决的挑战。具体来说，动态图建模和可视化算法的设计和实现可以对图论、计算几何、信息可视化和传感器网络产生影响。这项工作的中心概念是同时图嵌入、图变形和动态图。同时图嵌入是指两个或多个相关图的共同嵌入。对这个问题的研究涉及研究允许平面同时嵌入的图类的特征以及设计用于测试同时平面性的算法。图变形是指将给定的源图转换为另一个相关的目标图。对这个问题的研究包括设计用于欧几里德空间和黎曼空间变形的多项式时间算法，以及研究将重心坐标概念推广到非欧几里德空间的方法。可视化动态图需要能够实时处理大量数据，同时提供底层数据的信息表示。对这个问题的研究涉及开发有效且高效的动态图可视化算法，以及将新模型应用于移动传感器定位、机器人分散和地图构建。