I have two new preprints on arXiv, from my two papers accepted to Graph Drawing.

  • “Triangle-free penny graphs: degeneracy, choosability, and edge count” (arXiv:1708.05152) is a conference-paper version of an earlier post here, which showed that the triangle-free penny graphs are 2-degenerate. The main article is short but also expands on a comment I made on that post, a bound on the largest possible number of edges in these graphs that is close to the known lower bound. In an appendix, I also included material from two later posts here: some analogous results for squaregraphs, and a counterexample showing that the same results do not extend to arbitrary 2-degenerate triangle-free planar graphs.

  • “The effect of planarization on width” (arXiv:1708.05155) is an extended version of my answer to a cstheory question by Bart Jansen. Bart asked whether it is possible to draw \(K_{3,n}\) and then replace every crossing by a vertex, in such a way that the resulting planar graph has low pathwidth. The answer is no: every planarization of a drawing of \(K_{3,n}\) has pathwidth \(\Omega(n)\). The proof idea from that answer turns out to generalize to treewidth as well as pathwidth, and I also looked at the same question for many other graph width parameters. Some of these parameters behave like treewidth and pathwidth, blowing up when you planarize even as simple a graph as \(K_{3,n}\), while others stay bounded when you planarize a bounded-width graph. Here’s one of the figures from the planarization paper, a carving decomposition of \(K_{3,3}\) and its planarization:

Carving decomposition of K_{3,3} and its planarization

Graph Drawing has a policy of maintaining a shadow proceedings on arXiv.org, with the same content as the official proceedings, so I think we should be seeing quite a few more of these from other authors as the early-September proceedings deadline approaches.