Graph drawing addresses the problem of constructing geometric representations of graphs and networks. It is an emerging area of research that has received increasing attention both in the theory and systems community. From the theoretical viewpoint, graph drawing combines flavors of topological graph theory and computational geometry, and offers many algorithmic challenges. From the practical viewpoint, the automatic generation of drawings of graphs has important applications in key computer technologies such as software engineering, computer-aided-design, database systems, and visual interfaces. The research project addresses both theoretical and applied issues in graph drawing. Specific problems studied include: (1) Trade-offs between various properties of drawings, such as area, aspect-ratio, and angular resolution; (2) Upward planarity testing for directed graphs; (3) Dynamic planarity testing and incremental layout maintenance; (4) Three-dimensional drawing; (5) Declarative approaches to graph drawing and related constraint-satisfaction issues; (6) A graph visualization system and its applications.
