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.