Drawing Graphs with Low Visual Complexity

• Applicant: Professor Dr. André Schulz
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 256873462

In this project we study a novel design criterion for drawings of planar graphs. A common goal in graph drawing is to create visualizations that can be easily captured by the viewer. This includes, that the drawings of the edges and the vertices are well-distinguishable. From a classical point of view the realizations of the edges and vertices form the ground set of geometric objects, whose combination defines the drawing. In this project we investigate how one can construct drawings assembled from a very small ground set. The crucial point in our idea is that a simple path in the graph can be realized as a single object of the ground set. In this sense, we can obtain a drawing that uses fewer objects than it has edges. The drawing is therefore an arrangement of simple geometric objects, whose skeleton gives the input graph. We refer to the size of the ground set as the visual complexity of the drawing. As geometric objects we consider straight-line segments and circular arcs. We focus on drawings of planar graphs and study as subclasses trees, series-parallel graphs, outerplanar graphs, planar 3-trees and triangulations.We plan to develop algorithms for generating drawings with low visual complexity. The constructed drawings should also fulfill other well-established design criteria. In order to evaluate the quality of the constructed drawings we also study the worst-case visual complexity for planar graphs with respect to the number of edges. From this question we can derive a number of interesting combinatorial question in the area of graph theory, which we would like to investigate in this project. We claim that drawings with low visual complexity are esthetically appealing. We plan to verify our claim by empirical user studies. Moreover, we want to test if drawings with low visual complexity have other desirable properties. Finally, we would like to study the relationship between contact representations of circular arcs and drawings of graphs with low visual complexity.

• DFG Programme: Research Grants