Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Suggested Topics for Theses

The structure of split planar graphs

Let G be a directed graph. The split graph of G is a bipartite undirected graph defined as follows: For every node v of G, there are two nodes vout and vin. If there is a directed edge (u,v) in G, then the split graph contains the edge {uout, vin}. We call a directed graph split planar if its split graph is planar. Split planar graphs play an important role in the design of holographic algorithms for directed graphs.

The aim of this thesis is to better understand the relation between planar and split planar graphs. We have examples of non-planar graphs that are split planar and vice versa, but beyond this, not much is known.

Contact: Prof. Dr. Markus Bläser