Research Interests

Therese Biedl

I love to study algorithms, in particular if it involves drawing lots of pretty pictures when designing them. Specifically, I am interested in graph drawing, computational geometry, and algorithms for planar graphs.

My first research work was in Graph Drawing . We are given a graph for which we want to create a "nice" drawing. This has applications in many areas of computer science, such as software engineering, databases, decision support systems, as well as in other sciences such as biology and chemistry. Part of the problem is to define what is meant by a "nice" drawing. During my graduate studies I developed a number of results for orthogonal graph drawing, i.e., the style in which the graph is embedded into a rectangular grid. Since then, I have focused more on three-dimensional graph drawing, and other graph drawing styles. However, orthogonal graph drawings continue to haunt me (to the point that I sometimes believe that my brain is wired orthogonally).

Some people claim that graph drawing is a subfield of Computational Geometry. I don't want to voice an opinion of this, but regardless, this is also a field I'm interested in. Geometrical problems are frequently solved by converting the continuous geometrical structure into a discrete problem, which can then be formulated as a graph problem, and solved with graph algorithms. In particular, I have studied areas of Computational Geometry that involve origami-type questions (in particular, folding of linkages and surfaces) and motion planning.

I enjoy working with graphs, in particular planar graphs, and developing Graph Algorithms. Lately, I have been studying problems of the following type. Every planar graph has a 4-coloring of the vertices. From this 4-coloring, a number of interesting features can be obtained. For example, every planar graph has an independent vertex set of size n/4, every bridgeless 3-regular graph has a perfect matching, and every planar graph can be made bipartite by deleting at most m/3 edges. The 4-coloring of a planar graph can be found in O(n2) time, but the algorithm is not very practical, since the constants involved are huge. Which of the derived (and weaker) properties of a planar graph can be obtained without computation of a 4-coloring, and ideally in less time? In particular, I am interested in matching problems and independent sets.

In my spare time, I also like to think about Computational Biology, Data Structures, and VLSI design.