I’m gradually shifting weight to my Mastodon account and away from my doomed G+, but I hope to stick with both through the end of the year to provide a gradual transition. Today’s step: the Mastodon links go first.

• ## Gurobi versus the no-three-in-line problem

For the no-three-in-line problem, it has been known since the 1990s that $n\times n$ grids with $n\le 46$ have sets of $2n$ points with no three in line. Those results, by Achim Flammenkamp, were based on custom search software and a lot of compute time. I was curious to see how far one could get with more-modern but generic optimization codes, so this weekend I ran a little experiment.

• ## Random no-three-in-line sets

The UCI algorithms, combinatorics and optimization seminar this week featured a nice talk by local mathematician Nathan Kaplan on the no-three-in-line problem, which asks how many points you can choose from an $n\times n$ grid so that no three of them lie on a single line. For small $n$, such as the $10\times 10$ grid below, the answer is $2n$ (any more than that would lead to three points on a horizontal line) but it has long been conjectured that large enough grids have fewer points in their optimal solutions.

• ## 95 women of STEM

As they did last February, Wikipedia’s WikiProject Women in Red just finished another successful monthly editathon for October, centered on Women in STEM. I didn’t quite make my goal of contributing 100 new articles, but I came close. Here are the new articles I added:

• ## Layered pathwidth and its obstacles

There is a strong connection between the structural properties of the graphs in minor-closed families of graphs, and the properties of the graphs that are not in those families, their forbidden minors. A famous example of this is the proof by Robertson and Seymour (1986) that a minor-closed family of graphs has bounded treewidth if and only if at least one planar graph is not in the family. This is closely related to an earlier theorem of Halin on grid minors in infinite graphs, and Chekuri and Chuzhoy (STOC 2014) have proven a polynomial relation between the treewidth and the size of the excluded planar graph.

• ## Laminar 3-separators

My upcoming SODA paper with Bruce Reed, “Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time”, is now online as arXiv:1810.07825. It’s about algorithms that work only on planar graphs, but one of its main motivations is as a subroutine in a different algorithm for a problem on non-planar graphs. How can that be?

Because Google+ has been scheduled for shutdown (see item below), I’ve started cross-posting links to my Mastodon account @11011110@mathstodon.xyz in the hope that this gives me a smooth transition plan when the shutdown occurs. It also lets me put math formulas into my posts! Those new cross-posts are where the little $\mathbb{M}$ links on some of the entries below go. So if you want to see these postings when I make them, rather than these later roundups, follow me there.
I’ve written about Courcelle’s theorem here several times before. It’s a powerful “algorithmic meta-theorem” that lets you turn a logical characterization of a graph property into an algorithm for testing the property that runs in linear time in the input graphs size, for graphs of bounded treewidth. Unfortunately the constant factor of the linear time bound depends badly on the treewidth. In past posts, I’ve used this to formulate algorithms for minimal-crossing book embeddings, graph toughness, splitting vertices to make graphs planar, finding $k$ shortest paths, and constructing clustered planar drawings. My latest preprint, “Parameterized Leaf Power Recognition via Embedding into Graph Products” (arXiv:1810.02452, with UCI student Elham Havvaei, to appear in the proceedings of IPEC 2018) applies the same method to the problem of recognizing leaf powers.