David Eppstein – Publications

Publications with Erin Chambers

• Flows in one-crossing-minor-free graphs.
  E. Chambers and D. Eppstein.
  arXiv:1007.1484.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 241–252.
  J. Graph Algorithms and Applications 17 (3): 201–220, 2013.

  We show that the maximum flow problem can be solved in near-linear time for K₅-minor-free and K_3,3-minor-free graphs. The same result also holds for H-minor-free graphs when H can be embedded in the plane with one crossing and a structural decomposition of the input flow graph is given.

• Drawing graphs in the plane with a prescribed outer face and polynomial area.
  E. Chambers, D. Eppstein, M. T. Goodrich, and M. Löffler.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 129–140.
  arXiv:1009.0088.
  J. Graph Algorithms and Applications 16 (2): 243–259, 2012.

  Tutte's method of spring embeddings allows any triangulated planar graph to be drawn so that the outer face has any pre-specified convex shape, but it may place vertices exponentially close to each other. Alternative graph drawing methods provide polynomial-area straight line drawings but do not allow the outer face shape to be specified. We describe a drawing method that combines both properties: it has polynomial area, and can match any pre-specified shape of the outer face, even a shape in which some of the vertices have 180 degree angles. We apply our results to drawing polygonal schemas for graphs embedded on surfaces of positive genus.

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

• Low-stretch spanning trees of graphs with bounded width.
  G. Borradaile, E. Chambers, D. Eppstein, W. Maxwell, and A. Nayyeri.
  arXiv:2004.08375.
  Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
  Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19.

  We describe a random distribution on the spanning trees of bounded-bandwidth graphs such that each edge has bounded expected stretch, along with several related results for other kinds of graph widths.