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(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?
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**.