patmorin @patmorin@mathstodon.xyz
New post: Orientations of infinite graphs, https://11011110.github.io/blog/2019/01/17/orientations-infinite-graphs.html
In many cases the existence of an orientation with desired properties can be reduced to its existence in finite subgraphs, using a mathod from Rado (1949).
Recently, Bekos et al made a major breakthrough, showing that planar graphs of bounded degree have bounded queue number.
https://arxiv.org/abs/1811.00816
We were able to generalize this to bounded degree bounded genus graphs.
A recent arXiv preprint on robust spanners. For any \(n\)-point set in \(\mathbb{R}ᵈ\), we show how to construct spanners with \(O(n\log²n\log\log n)\) edges so that, if you remove \(k\) vertices, the remaining graph is a spanner of \(n-(1+ε)k\) of its vertices.
https://arxiv.org/abs/1812.09913
We called these \((1+ε)k\)-robust spanners. Buchin, Har-Peled, and Olah have a much catchier name: 'a spanner for the day after'
New post: Gurobi versus the no-three-in-line problem
https://11011110.github.io/blog/2018/11/12/gurobi-vs-no.html
How well can a good but generic integer linear program solver stand up against 20-year-old problem-specific search code?
Two new arXiv preprints:
https://arxiv.org/abs/1811.03432
https://arxiv.org/abs/1811.03427
The first shows that if a graph \(G\) has a non-crossing straight-line drawing (a.k.a. Fáry drawing) in which some set \(S\) of vertices is drawn on a single line then, for any point set \(X\) of size \(|S|\), \(G\) has a Fáry drawing in which the vertices in \(S\) are drawn on the points in \(X\).
The second shows that, in bounded degree planar graphs, one can always find such a set \(S\) of size \(\Omega(n^{0.8})\).
