David Eppstein – Publications

Publications with Victor Chepoi

• Combinatorics and geometry of finite and infinite squaregraphs.
  H.-J. Bandelt, V. Chepoi, and D. Eppstein.
  arXiv:0905.4537.
  SIAM J. Discrete Math. 24 (4): 1399–1440, 2010.

  Characterizes squaregraphs as duals of triangle-free hyperbolic line arrangements, provides a forbidden subgraph characterization of them, describes an algorithm for finding minimum subsets of vertices that generate the whole graph by medians, and shows that they may be isometrically embedded into Cartesian products of five (but not, in general, fewer than five) trees.

• Ramified rectilinear polygons: coordinatization by dendrons.
  H.-J. Bandelt, V. Chepoi, and D. Eppstein.
  arXiv:1005.1721.
  Disc. Comp. Geom. 54 (4): 771–797, 2015.

  We characterize the graphs that can be isometrically embedded into the Cartesian product of two trees (partial double dendrons), and the metric spaces obtained as the median complexes of these graphs. These spaces include the space of geodesic distance in axis-parallel polygons in the L₁ plane, hence the title. An algorithm based on lexicographic breadth-first search can be used to recognize partial double dendrons in linear time.