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

“Trianglefree penny graphs: degeneracy, choosability, and edge count” (arXiv:1708.05152) is a conferencepaper version of an earlier post here, which showed that the trianglefree penny graphs are 2degenerate. 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 2degenerate trianglefree 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 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 has pathwidth . 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 , while others stay bounded when you planarize a boundedwidth graph. Here’s one of the figures from the planarization paper, a carving decomposition of 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 earlySeptember proceedings deadline approaches.
(G+)