University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Graduation Talks

title

Tools for Planar Drawings of Graphs and Hypergraphs

speaker

Melanie Badent, University Konstanz
Konstanz, Germany

date & place

Wednesday, 13.01.2010, 16:00 h
Room C252

abstract

Planar drawings are layouts of planar graphs and their computation is of particular importance. In this thesis, we first study algorithms that can be used as fundamental components in various methods for planar drawings of graphs and then explore related concepts for hypergraphs.
A prerequisite of many planar layout algorithms is an appropriate processing sequence of the vertices. Prominent examples are topological ordering, canonical ordering, and st-ordering. We present a simplified linear-time algorithm that computes a unique canonical ordering of a triconnected planar graph. A natural generalization of canonical orderings are st-orderings on biconnected graphs that can be determined from special potential equations. We plan to investigate how a similar concept can be used to enumerate all canonical orderings.
Blocks on hypergraphs play a similar role like biconnected components on planar graphs. Currently, we are developing a linear-time algorithm that extends the biconnected components of a graph to a block decomposition of a hypergraph. The block decomposition is used to compute a cactus support. The research objective is to close the gap between the quadratic-time algorithm for a cactus support and the NP-completeness of the decision problem whether a hypergraph has a 2-outerplanar support.