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

Joined Oct 2018