David Eppstein - Publications

Circles, spheres, and sphere packing

• A deterministic linear time algorithm for geometric separators and its applications.
  D. Eppstein, G.L. Miller, and S.-H. Teng.
  9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 99–108.
  Fundamenta Informaticae 22: 309–330, 1995 (special issue on computational geometry).

  Teng and others previously showed that certain geometric graphs had small separators that could be found by lifting the graph to a sphere one dimension up and choosing a random great circle. Here we show that epsilon-cuttings and the method of conditional expectations can be used to guide a deterministic prune-and-search method for the same problem. Applications include finding the intersection graph of a collection of spheres and computing or approximating the maximum number of spheres having a common intersection.

• Faster circle packing with application to nonobtuse triangulation.
  D. Eppstein.
  Tech. Rep. 94-33, ICS, UCI 1994.
  Int. J. Comp. Geom. & Appl. 7 (5): 485–491, 1997.

  Speeds up a triangulation algorithm of Bern et al. ["Linear-Size Nonobtuse Triangulation of Polygons"] by finding a collection of disjoint circles which connect up the holes in a non-simple polygon. The method is to use a minimum spanning tree to find a collection of overlapping circles, then shrink them one by one to reduce the number of overlaps, using Sleator and Tarjan's dynamic tree data structure to keep track of the connectivity of the shrunken circles.

• Faster construction of planar two-centers.
  D. Eppstein.
  Tech. Rep. 96-12, ICS, UCI, 1996.
  8th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 1997, pp. 131–138.

  Improving on a recent breakthrough of Sharir, we use data structures from "Dynamic three-dimensional linear programming" to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(n log² n).

  (SODA paper – DREI and SODA talk slides)

• Quadrilateral meshing by circle packing.
  M. Bern and D. Eppstein.
  2nd CGC Worksh. Computational Geometry, Durham, North Carolina, 1997.
  6th Int. Meshing Roundtable, Park City, Utah, 1997, pp. 7–19.
  arXiv:cs.CG/9908016.
  Int. J. Comp. Geom. & Appl. 10 (4): 347–360, 2000.

  We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types:

  1. The elements form the cells of a Voronoi diagram,
  2. The elements each have two opposite 90 degree angles,
  3. All elements are kites, or
  4. All angles are at most 120 degrees.

  In each case the total number of elements is \(O(n)\). The 120-degree bound is optimal; if a simply-connected region has all angles at least 120 degrees, any mesh of that region has a 120 degree angle.

• A disk-packing algorithm for an origami magic trick.
  M. Bern, E. Demaine, D. Eppstein, and B. Hayes.
  Int. Conf. Fun with Algorithms, Elba, June 1998.
  Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 32–42.
  Origami³: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (Asilomar, California, 2001), A K Peters, 2002, pp. 17–28.

  We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.

• Tangent spheres and triangle centers.
  D. Eppstein.
  arXiv:math.MG/9909152.
  Amer. Math. Monthly 108 (1): 63–66, 2001.

  Any four mutually tangent spheres determine three coincident lines through opposite pairs of tangencies. As a consequence, we define two new triangle centers. These centers arose as part of a compass-and-straightedge construction of Soddy circles; also available are some Mathematica calculations of trilinear coordinates for the new triangle centers.

• Optimal Möbius transformations for information visualization and meshing.
  M. Bern and D. Eppstein.
  arXiv:cs.CG/0101006.
  7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 14–25.

  We give linear-time quasiconvex programming algorithms for finding a Möbius transformation of a set of spheres in a unit ball or on the surface of a unit sphere that maximizes the minimum size of a transformed sphere. We can also use similar methods to maximize the minimum distance among a set of pairs of input points. We apply these results to vertex separation and symmetry display in spherical graph drawing, viewpoint selection in hyperbolic browsing, and element size control in conformal structured mesh generation.

  (WADS talk slides)

• Fat 4-polytopes and fatter 3-spheres.
  D. Eppstein, G. Kuperberg, and G. Ziegler.
  arXiv:math.CO/0204007.
  Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Appl. Math. 253, Marcel Dekker, pp. 239–265, 2003.

  We introduce the fatness parameter of a 4-dimensional polytope P, (f₁+f₂)/(f₀+f₃). It is open whether all 4-polytopes have bounded fatness. We describe a hyperbolic geometry construction that produces 4-polytopes with fatness > 5.048, as well as the first infinite family of 2-simple, 2-simplicial 4-polytopes and an improved lower bound on the average kissing number of finite sphere packings in R³. We show that fatness is not bounded for the more general class of strongly regular CW decompositions of the 3-sphere.

• Diamond-kite meshes: adaptive quadrilateral meshing and orthogonal circle packing.
  D. Eppstein.
  arXiv:1207.5082.
  21st International Meshing Round Table, San Jose, California, 2012, pp. 261–277.
  Engineering with Computers 30 (2): 223–235 (special issue for the 21st Int. Meshing Roundtable), 2014.

  We describe a recursive subdivision of the plane into quadrilaterals in the form of rhombi and kites with 60, 90, and 120 degree angles. The vertices of the resulting quadrilateral mesh form the centers of a set of circles that cross orthogonally for every two adjacent vertices, and it has many other properties that are important in finite element meshing.

  (Slides)

• A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing.
  D. Eppstein.
  Invited talk at EuroGIGA Midterm Conference, Prague, Czech Republic, 2012.
  Discrete Comput. Geom. 52 (3): 515–550, 2014 (Special issue for SoCG 2013).

  This talk and journal paper combines the results from "Planar Lombardi drawings for subcubic graphs" and "The graphs of planar soap bubbles". It uses three-dimensional hyperbolic geometry to define a partition of the plane into cells with circular-arc boundaries, given an input consisting of (possibly overlapping) circular disks and disk complements, which remains invariant under Möbius transformations of the input. We use this construction as a tool to construct planar Lombardi drawings of all 3-regular planar graphs; these are graph drawings in which the edges are represented by circular arcs meeting at equal angles at each vertex. We also use it to characterize the graphs of two-dimensional soap bubble clusters as being exactly the 2-vertex-connected 3-regular planar graphs.

• Planar Lombardi drawings for subcubic graphs.
  D. Eppstein.
  arXiv:1206.6142.
  20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
  Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 126–137.
  

  We show that every planar graph of maximum degree three has a planar Lombardi drawing and that some but not all 4-regular planar graphs have planar Lombardi drawings. The proof idea combines circle packings with a form of Möbius-invariant power diagram for circles, defined using three-dimensional hyperbolic geometry.

  For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".

  (Slides)

• The graphs of planar soap bubbles.
  D. Eppstein.
  arXiv:1207.3761.
  Proc. 29th ACM Symp. on Computational Geometry, Rio de Janeiro, 2013, pp. 27–36.

  We characterize the graphs of two-dimensional soap bubble clusters as being exactly the bridgeless 3-regular planar graphs. The proof uses the Möbius invariance of the properties characterizing these clusters together with our previous circle packing method for constructing Lombardi drawings of graphs.

  For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".

  (Slides)

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

• The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings.
  M. J. Bannister, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
  arXiv:1408.1422.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 149–161.
  J. Graph Algorithms & Applications 19 (2): 619–656, 2015 (special issue for GD'14).

  We show that many standard graph drawing methods have algebraic solutions described by polynomials that can have unsolvable Galois groups, and that can have Galois groups whose order is divisible by large prime numbers. As a consequence certain models of exact algebraic computation are unable to construct these drawings.

• Balanced circle packings for planar graphs.
  M. J. Alam, D. Eppstein, M. T. Goodrich, S. Kobourov, and S. Pupyrev.
  arXiv:1408.4902.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 125–136.

  The balanced circle packings of the title are systems of interior-disjoint circles, whose tangencies represent the given graph, and whose radii are all within a polynomial factor of each other. We show that these packings always exist for trees, cactus graphs, outerpaths, k-outerplanar graphs of bounded degree when k is at most logarithmic, and planar graphs of bounded treedepth. The treedepth result uses a new construction of inversive-distance circle packings.

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

  (Slides)

• Triangle-free penny graphs: degeneracy, choosability, and edge count.
  D. Eppstein.
  arXiv:1708.05152.
  Proc. 25th Int. Symp. Graph Drawing, Boston, Massachusetts, 2017.
  Springer, Lecture Notes in Comp. Sci. 10692 (2018), pp. 506–513.
  J. Graph Algorithms & Applications 22 (3): 483–499 (special issue for GD 2017), 2018.

  A penny graph is the contact graph of unit disks: each disk represents a vertex of the graph, no two disks can overlap, and each tangency between two disks represents an edge in the graph. We prove that, when this graph is triangle free, its degeneracy is at most two. As a consequence, triangle-free penny graphs have list chromatic number at most three. We also show that the number of edges in any such graph is at most 2n − Ω(√n). The journal version uses the alternative title "Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs".

  (Slides)

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