David Eppstein - Publications

Publications with Therese Biedl

• 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.

• On the complexity of embedding in graph products.
  T. Biedl, D. Eppstein, and T. Ueckerdt.
  arXiv:2303.17028.
  Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 77–88.
  Computing in Geometry and Topology 4 (2): 5:1–5:18, 2025.

  Row treewidth (embedding a graph as a subgraph of a strong product of a path with a low treewidth graph), row pathwidth, and row tree-depth are all NP-hard.