Two papers of mine on the arxiv, one a few weeks old and one newly appearing:
- Optimal angular resolution for face-symmetric drawings
(with Kevin Wortman). In this paper, we consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media from Graph Drawing 2004. Among all drawings of this type, we show how to find the one with optimal angular resolution. The specific motivation was to improve the drawing I showed in this post to be more legible, so that it could be used in my recent paper on squaregraphs with Bandelt and Chepoi. The solution involves the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. However, unlike my work with Kevin on metric embedding, the parametric graph coming from this problem falls into a special case solved by known algorithms, so we didn't need to invent a new cycle detection algorithm. We're preparing a version of this for journal publication, but the current version doesn't yet have all of the referee's requested revisions incorporated, because I wanted to have a version of this available in order to cite it from the next one:
- Graph-theoretic solutions to computational geometry problems.
A survey on situations in which geometric problems that are stated without reference to any graph can be solved efficiently by defining some auxiliary graph from the input and performing some graph-theoretic algorithm. For instance, the problem of partitioning a polygon with axis-parallel sides into as few rectangles as possible may be solved in polynomial time by constructing the bipartite intersection graph of its axis-aligned diagonals and finding a maximum matching in this graph. Essentially, this is a paper version of my talk from WG, and I wrote it backwards from the way I usually write papers and talks: usually I write a paper, then later (after it is accepted to a conference) write slides based on that paper, and deliver a talk based on those slides. But this time, I had no paper written when I needed the slides and a talk, so I worked out how to organize the material as part of the process of making slides and giving the talk, and reused the same organization for the paper itself. I used to write survey papers regularly, but lately I've tended to focus that energy on my Wikipedia editing, so it was refreshing to write something like this and not feel constrained to avoid including original research (such as the claim that kinggraphs are 4-chromatic) or original syntheses of existing ideas (the overall point of the survey).