While I've been at SODA one of my co-authors has been busy preparing what turns out to be my first preprint of the new year: Contact Representations of Sparse Planar Graphs (arXiv:1501.00318, with Alam, Kaufmann, Kobourov, Pupyrev, Schulz, and Ueckerdt). I think this is one of these cases where a picture can go a lot farther than words in explaining: here's an example of what we're looking at.

Graph of the cuboctahedron, represented as a circular-arc contact system

The 12 circular arcs of this diagram correspond to the 12 vertices of a cuboctahedron, and the 24 contact points between arcs (the points where one arc ends as it runs into another arc) correspond to the 24 edges of the cuboctahedron. What we want to know is which other graphs can be represented like the cuboctahedron in this way? They have to be planar, and every subgraph has to have at most twice as many edges as vertices (because every set of arcs has twice as many endpoints as arcs) and beyond that it's a little mysterious. But we have some natural subclasses of the planar graphs for which we can prove that such a representation always exists (for instance the 4-regular planar graphs) and some NP-hardness results.

Two other uploads of possible interest: my report as co-PC-chair at the ALENEX business meeting, and my talk on Miura folding (both with small corrections to the slides I actually used). I've posted here before about the Miura folding results. For the ALENEX report, besides the usual breakdown of acceptance rates and subtopics, there were two more substantial issues for future planning: should ALENEX move its submission deadline earlier than the SODA notification date (so that the PC has adequate time to review the submissions), and should it accept more papers? The sentiment at the meeting seemed to be in favor of both ideas.