CAREER: Embedding, Morphing, and Visualizing Dynamic Graphs

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

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.