I’m at the University of Waterloo, as the external examiner at Martin Derka’s Ph.D. defense, which he just passed, with Therese Biedl as his advisor.

Derka’s dissertation consists of a significant body of novel research on string graphs, a class of graphs that can be represented by intersections of curves (“strings”) or other connected objects in the plane. These graphs are very general and encompass many other important graph classes. Some of Derka’s main results are:

  • Every planar graph can be represented by strings that simultaneously avoid multiple crossings and consist of axis-parallel line segments with at most two bends. Both properties were known separately but not simultaneously. Some important subclasses of planar graph can be represented with only one bend.

  • Every axis-parallel string graph with few bends can be partitioned into a polylogarithmic number of permutation graphs, and this partition leads to new approximation algorithms for maximum independent set, minimum coloring, maximum clique, and minimum clique cover.

  • 1-planar graphs (the graphs that can be drawn with at most one crossing per edge) with an extra restriction, that no two crossing edges induce a matching, are string graphs but may require more than one crossing per string.

  • Outer-string graphs (the string graphs that can be drawn with all strings having an endpoint on the outer face) may also sometimes require exponentially many string crossings.

Congratulations, Martin!