Graph Visualization and Geometric Algorithm Design

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

Proposal #0098068Michael T. GoodrichJohns Hopkins UniversityThis project is focused on the development of data structures and algorithms for performing computations involving the representation, transformation, and visualization of collections of objects that can be modeled geometrically, such as vertices, edges, lines, planes, polygons, curves, and spheres. In particular, it addresses the following topics:1. Graph visualization: the design of efficient data structures and algorithms for efficiently representing and visualizing relational information.2. Geometric algorithms: the development of efficient algorithms for solving problems involving geometric data, particularly for problems related to graph visualization.3. Geometric data structures: the design of fast and efficient data structures for representing graphs and sets of geometric objects.4. JDSLviz: the implementation of a prototype of a Java library of algorithms for graph visualization. Building on our existing JDSL library of fundamental data structures in Java, we shall identify algorithm engineering design patterns for the geometric computations performed in graph drawing, and implement fundamental graph visualization algorithms as reusable software components.5. GraphNet: the implementation of an Internet computing infrastructure for graph visualization. Extending previous work on the GeomNet system for geometric computing over the Internet, we plan to build a prototype of a novel Web-based graph layout service in the ASP (application service provider) model.The main objective of this work is the development of general methodologies for the design of geometric data structures and algorithms, as well as their incorporation into software libraries and internet computing services. This work has potential impact in areas of science and engineering that model physical objects or that use geometry for information visualization.