Application of the point-line duality principle in graph drawing

VCLA hosted a talk by Tamara Mchedlidze

ABSTRACT

In practice it can happen that several sets of pairwise ordered relations are defined on the same set of elements. For example, consider a set of employees in a company. They are typically related by the hierarchy established within the company. On the other hand, their actual connections during a day (emails, phones) define another set of ordered relations among them.  When each set of ordered pairwise relations is modeled as a directed graph, we obtain several directed graphs sharing the same vertex set. In our example, the vertices are the employees, the edges of one graph are defined by the hierarchy within the company, and the edges of the other graph by the connections during a day.

To analyze, to compare and to understand this information, we can explore a 2- or even 3-dimensional visual representation of it. Here monotone simultaneous embeddings of graphs come into play. In a monotone simultaneous embeddings the vertices are positioned on the plane or in the 3-dimensional space as points so that edges of each graph, when drawn as straight-line arcs, point into the same direction. This property facilitates the understanding of the hierarchy explained by each graph.

In this presentation I will talk about application of a basic projective geometry tool, the point-line duality principle, to the problem of construction of monotone simultaneous embedding of several directed graphs on the plane. Afterwards, we will see the generalization of this application to the 3-dimensional space.

Dr. Tamara Mchedlidze is a computer scientists interested in algorithms, graphs and their visualizations.

Dr. Mchedlidze studies formally defined network visualization problems, their computational complexity, and formally proves quality guarantees for the layouts produced by the algorithms. From the practical perspective, she studies the performance of the algorithms experimentally and assesses the quality of the network visualizations empirically. Currently, in a collaboration with philosophers, Dr. Mchedlidze works in an interdisciplinary project, that includes modelling and visualization of large dynamic debates in form of networks. The intermediate result of this project is exhibited in ZKM | Center for Art and Media in Karlsruhe.

Dr. Tamara Mchedlidze grew up in Tbilisi, Georgia. She studied and obtained her PhD from the faculty of Applied Mathematics and Physical Sciences of National Technical University of Athens, Greece.  Since 2012 she is a postdoctoral researcher at the Institute of Theoretical Informatics, in Karlsruhe Institute of Technology, Germany.

Tamara Mchedlidze, Karlsruhe Institute of Technology (KIT)