Graph Drawing

图形绘制解决了构建图形和网络的几何表示的问题。 它是一个新兴的研究领域，在理论界和系统界都受到越来越多的关注。 从理论的角度来看，图形绘制结合了拓扑图论和计算几何的风格，并提供了许多算法的挑战。 从实用的角度来看，图形的自动生成在软件工程、计算机辅助设计、数据库系统和可视化界面等关键计算机技术中具有重要的应用。 该研究项目涉及图形绘制的理论和应用问题。 研究的具体问题包括：（1）绘图的各种属性之间的权衡，例如面积、纵横比和角分辨率;（2）有向图的向上平面性测试;（3）动态平面性测试和增量布局维护;（4）三维绘图;（5）图形绘制的声明性方法和相关的约束满足问题;（6）图形可视化系统及其应用。

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.