patmorin boosted

New post: Orientations of infinite graphs, 11011110.github.io/blog/2019/0

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.

arxiv.org/abs/1811.00816

We were able to generalize this to bounded degree bounded genus graphs.

arxiv.org/pdf/1901.05594.pdf

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.

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'

arxiv.org/abs/1811.06898

patmorin boosted

New post: Gurobi versus the no-three-in-line problem
11011110.github.io/blog/2018/1

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:

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})$.

A Mastodon instance for maths people. The kind of people who make $\pi z^2 \times a$ jokes.

Use $ and $ for inline LaTeX, and $ and $ for display mode.