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. One
of my more recent endeavors have been approximation algorithms in
graph drawing. For example, if we are given a planar graph, can we
find a planar straight-line drawing whose height is at most *k* times
(for some constant *k*) the minimum possible height? This is still
open for all planar graphs, but progress has been made for various subclasses
such as trees, outer-planar graphs, Halin-graphs etc.

I enjoy working with graphs, in particular planar graphs, and
developing ** Graph
Algorithms**,
especially for combinatorial problems such as matching and independent sets.
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(n^{2})
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?

There are also many graphs that are not planar but "close" to planar graphs
in some sense. For example the 1-planar graphs are the graphs that have a
drawing with at most one crossing per edge. Some algorithms for planar graphs
carry over to 1-planar graphs in a straightforward way, but many algorithms
do not, and we must separately solve them for 1-planar graphs.

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 morphing (e.g., linkage-folding or morphing
graph drawings) and other problems involve graphs and trees,
such as Delauney triangulations and straight skeletons.

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