David Eppstein – Publications

Publications with Tim Ophelders

Homotopy height, grid-minor height and graph-drawing height.
T. Biedl, E. Chambers, D. Eppstein, A. de Mesmay, and T. Ophelders.
arXiv:1908.05706.
Proc. 27th Int. Symp. Graph Drawing, Prague, Czech Republic, 2019.
Springer, Lecture Notes in Comp. Sci. 11904 (2019), pp. 468–481.

We lower bound the height of a drawing of a planar graph in an integer grid by a topological invariant, the homotopy height, and show that this invariant is equal to the smallest height of a grid graph in which the given graph is a minor.