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.