A counterexample to the Ringel circle problem: https://arxiv.org/abs/2112.05042, via https://gilkalai.wordpress.com/2021/12/11/to-cheer-you-up-in-difficult-times-34-ringel-circle-problem-solved-by-james-davies-chaya-keller-linda-kleist-shakhar-smorodinsky-and-bartosz-walczak/

Ringel asked whether systems of circles, tangent only in pairs, can be colored with O(1) colors so no two tangent circles have the same color. Five colors were known to be necessary but unknown to be sufficient; see the lead image of my old web page https://www.ics.uci.edu/~eppstein/junkyard/tangencies/

Now Davies, Keller, Kleist, Smorodinsky, and Walczak have found systems of circles requiring arbitrarily many colors.

TheoretiCS, a new diamond-open-access journal in all areas of theoretical computer science: https://theoretics.episciences.org/

It is being run as an overlay of arXiv, through the Episciences platform for such overlays, with Javier Esparza and Uri Zwick as editors-in-chief and a large and distinguished editorial board.

Five talks from CanaDAM 2021 introducing graph product structure theory and its applications:

This is probably the best / quickest introdoctrination to the topic currently available.

An implementation of the Product Structure Theorem for planar graphs, in Python:

https://github.com/patmorin/lhp

Not exactly industrial-strength, and leans towards simplicity over performance. Still, it can decompose 100k-vertex triangulations in a few seconds. I'm open to feature requests.

New blog post, Hex, books, and queues: https://11011110.github.io/blog/2020/11/10/hex-books-queues.html

And new arXiv preprint, Stack-number is not bounded by queue-number (with Vida Dujmović, Robert Hickingbotham, Pat Morin, and David R. Wood), https://arxiv.org/abs/2011.04195

if you like well-quantified risk info

https://www.erinbromage.com/post/the-risks-know-them-avoid-them

Congratulations to my (now former) student, Luís Fernando Schulz Xavier da Silveira, who successfully defended his PhD thesis titled Turán Triangles, Cell Covers, Road Placement and Train Scheduling on Monday.

This is the first thesis defense I've taken part in where no two participants were in the same room.

Congratulations to our student (cosupervised with Vida Dujmović) Céline Yelle who just masterfully defended her Master's thesis titled Stack Number, Track Number, and Layered Pathwidth.

The thesis contains two results:

1. \(\mathrm{sn}(G) \le 4\mathrm{lpw}(G) \)

2. \(\mathrm{tn}(G)\le 3\) implies \(\mathrm{lpw}(G)\le 4\).

Planar graphs (and related families of graphs) have \((1+o(1))\log n\)-bit adjacency labelling schemes. Equivalently, there is a graph with \(n^{1+o(1)}\) vertices that contains every \(n\)-vertex planar graph as an induced subgraph.

https://arxiv.org/abs/2003.04280

The proof combines our year-old product structure theorem with binary search trees!

Professor of Computer Science at Carleton University

Joined Oct 2018