David Eppstein - Publications

Electronic Journal of Combinatorics

• Cubic partial cubes from simplicial arrangements.
  D. Eppstein.
  arXiv:math.CO/0510263.
  Electronic J. Combinatorics 13(1), Paper R79, 2006.

  We show how to construct a cubic partial cube from any simplicial arrangement of lines or pseudolines in the projective plane. As a consequence, we find nine new infinite families of cubic partial cubes as well as many sporadic examples.

• The Fibonacci dimension of a graph.
  S. Cabello, D. Eppstein, and S. Klavžar.
  IMFM Preprint 1084, Institute of Mathematics, Physics and Mechanics, Univ. of of Ljubljana, 2009.
  arXiv:0903.2507.
  Electronic J. Combinatorics 18(1), Paper P55, 2011.

  We investigate isometric embeddings of other graphs into Fibonacci cubes, graphs formed from the families of fixed-length bitstrings with no two consecutive ones.

• Densities of minor-closed graph families.
  D. Eppstein.
  arXiv:1009.5633.
  Electronic J. Combinatorics 17(1), Paper R136, 2010.

  For every minor-closed graph family (such as the family of planar graphs), there is a constant c such that the maximum number of edges in an n-vertex graph in the family is c(n + o(n); for instance, for planar graphs, c = 3. We call c the limiting density of the family, and we study the set of all limiting densities of all minor-closed graph families. We show that this set of limiting densities is closed and well-ordered, with order type at least ω^ω, and we find an exact description of the members of this set up to its first two cluster points 1 and 3/2.

• Grid minors in damaged grids.
  D. Eppstein.
  arXiv:1303.1136.
  Electronic J. Combinatorics 21(3), Paper P3.20, 2014.

  We give tight bounds on the size of the largest remaining grid minor in a grid graph from which a given number of vertices have been deleted, and study several related problems.

• Existence and hardness of conveyor belts.
  M. Baird, S. C. Billey, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, G. Gordon, S. Griffin, J. S. B. Mitchell, and J. P. Swanson.
  arXiv:1908.07668.
  Electronic J. Combinatorics 27 (4), Paper P4.25, 2020.

  A conveyor belt is a tight simple closed curve that touches each of a given set of disjoint disks. We show that certain special families of disks always have a conveyor belt, but that it is NP-complete to tell whether one exists for arbitrary families of disks. It is always possible to add a linear number of "guide disks" to a given set of disks to allow them to be connected by a conveyor belt.