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²) 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.