David Eppstein – Publications

J. Computational Geometry

• Happy endings for flip graphs.
  D. Eppstein.
  arXiv:cs.CG/0610092.
  23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 92–101.
  J. Computational Geometry 1 (1): 3–28, 2010.

  We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.

• Optimally fast incremental Manhattan plane embedding and planar tight span construction.
  D. Eppstein.
  arXiv:0909.1866.
  J. Computational Geometry 2 (1): 144–182, 2011.

  Shows that, when the tight span of a finite metric space is homeomorphic to a subset of the plane, it has the geometry of a Manhattan orbifold and can be constructed in time linear in the size of the input distance matrix. As a consequence, it can be tested in the same time whether a metric space is isometric to a subset of the L₁ plane.

• Steinitz theorems for orthogonal polyhedra.
  D. Eppstein and E. Mumford.
  arXiv:0912.0537.
  26th Eur. Worksh. Comp. Geom., Dortmund, Germany, 2010.
  26th ACM Symp. Comp. Geom., Snowbird, Utah, 2010, pp. 429–438.
  J. Computational Geometry 5 (1): 179–244, 2014.

  We provide a graph-theoretic characterization of three classes of nonconvex polyhedra with axis-parallel sides, analogous to Steinitz's theorem characterizing the graphs of convex polyhedra.

  The journal version has the slightly different title "Steinitz theorems for simple orthogonal polyhedra".

  (SoCG'10 slides)

• Adjacency-preserving spatial treemaps.
  K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg, and R. I. Silveira.
  arXiv:1105.0398.
  12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011.
  Springer, Lecture Notes in Comp. Sci. 6844, 2011, pp. 159–170.
  J. Computational Geometry 7 (1): 100–122, 2016.

  We study the recursive partitions of rectangles into sets of rectangles, and partitions of those rectangles into smaller rectangles, to form stylized visualizations of hierarchically subdivided geographic regions. There are several variations of varying difficulty depending on how much of the geographic information from the input we require the output to preserve.

• Planar and poly-arc Lombardi drawings.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Löffler, and M. Nöllenburg.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 308–319.
  arXiv:1109.0345.
  J. Computational Geometry 9 (1): 328–355, 2018.

  We extend Lombardi drawing (in which each edge is a circular arc and the edges incident to a vertex must be equally spaced around it) to drawings in which edges are composed of multiple arcs, and we investigate the graphs that can be drawn in this more relaxed framework.

• Strict confluent drawing.
  D. Eppstein, D. Holten, M. Löffler, M. Nöllenburg, and B. Speckmann, and K. Verbeek.
  arXiv:1308.6824.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 352–363.
  J. Computational Geometry 7 (1): 22–46, 2016.

  A confluent drawing of a graph is a set of points and curves in the plane with the property that two vertices are adjacent in the graph if and only if the corresponding points can be connected to each other by smooth paths in the drawing. We define a variant of confluent drawing, strict confluent drawing, in which a smooth path between two vertices (if it exists) must be unique. We show that it is NP-complete to test whether such drawings exist, in contrast to unrestricted confluence for which the complexity remains open. Additionally, we show that finding outerplanar drawings (in which the points are on the boundary of a disk and the curves are interior to it) with a fixed cyclic vertex ordering can be performed in polynomial time. We use circle packings to find nice versions of these drawings in which all tracks are represented by piecewise-circular curves.

• Flat foldings of plane graphs with prescribed angles and edge lengths.
  Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.
  arXiv:1408.6771.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 272–283.
  J. Computational Geometry 9 (1): 74–93, 2018.

  Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.

• Approximate greedy clustering and distance selection for graph metrics.
  D. Eppstein, S. Har-Peled, and A. Sidiropoulos.
  arXiv:1507.01555.
  J. Computational Geometry 11 (1): 629–652, 2020.

  We provide fast approximation algorithms for the farthest-first traversal of graph metrics.

• Rigid origami vertices: Conditions and forcing sets.
  Z. Abel, J. Cantarella, E. Demaine, D. Eppstein, T. Hull, J. Ku, R. Lang, and T. Tachi.
  arXiv:1507.01644.
  J. Computational Geometry 7 (1): 171–184, 2016.

  We give an exact characterization of the one-vertex origami folding patterns that can be folded rigidly, without bending the parts of the paper between the folds.

• Maximizing the sum of radii of disjoint balls or disks.
  D. Eppstein.
  arXiv:1607.02184.
  Proc. 28th Canadian Conference on Computational Geometry, Vancouver, BC, Canada, 2016, pp. 260–265.
  J. Computational Geometry 8 (1): 316–339, 2017.

  We show how to find a system of disjoint balls with given centers, maximizing the sum of radius of the balls. Our algorithm takes cubic time in arbitrary metric spaces and can be sped up to subquadratic time in Euclidean spaces of any bounded dimension.

  (CCCG'16 slides)

• Covering many points with a small-area box.
  M. De Berg, S. Cabello, O. Cheong, D. Eppstein, and C. Knauer.
  arXiv:1612.02149.
  J. Computational Geometry 10 (1): 207–222, 2019.

  We give an efficient algorithm for finding the smallest axis-parallel rectangle covering a given number of points out of a larger set of points in the plane.

• Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.
  G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.
  arXiv:1804.09411
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 89:1–89:14.
  J. Computational Geometry 11 (1): 26–59, 2020.

  The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.

• Realization and connectivity of the graphs of origami flat foldings.
  D. Eppstein.
  arXiv:1808.06013.
  Proc. 26th Int. Symp. Graph Drawing, Barcelona, 2018.
  Springer, Lecture Notes in Comp. Sci. 11282 (2018), pp. 541–554.
  J. Computational Geometry 10 (1): 257–280, 2019.

  If you fold a piece of paper flat and unfold it again, the resulting crease pattern forms a planar graph. We prove that a tree can be realized in this way (with its leaves as diverging rays that reach the boundary of the paper) if and only if all internal vertices have odd degree greater than two. On the other hand, for a folding pattern on an infinite sheet of paper with an added vertex at infinity as the endpoint of all its rays, the resulting graph must be 2-vertex-connected and 4-edge-connected.

  (GD'18 slides)

• Cubic planar graphs that cannot be drawn on few lines.
  D. Eppstein.
  arXiv:1903.05256.
  Proc. 35th Int. Symp. on Computational Geometry, Portland, Oregon, June 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 129, 2019, pp. 32:1–32:15.
  J. Computational Geometry 12 (1): 178–197, 2021.

  We construct planar graphs whose straight drawings require a large number of lines (at least the cube root of the number of vertices) to cover all vertices. We also find series-parallel graphs and apex-trees that require a non-constant number of lines.

  (SoCG'19 slides)

• Face flips in origami tessellations.
  H. A. Akitaya, V. Dujmović, D. Eppstein, T. Hull, K. Jain, and A. Lubiw.
  arXiv:1910.05667.
  J. Computational Geometry 11 (1): 397–417, 2020.

  We study problems in which we are given an origami crease pattern and seek to reconfigure one locally flat foldable mountain-valley assignment into another by a sequence of operations that change the assignment around a single face of the crease pattern.