Graph Drawing with Low Visual Complexity (GRANVK)

Basic data for this project

Type of project: Own resources project
Duration: 01/11/2014 - 31/10/2018

Description

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.

Keywords: graph drawing; graph theory; algorithms