David Eppstein - Publications

2010

• Dynamic graph algorithms.
  D. Eppstein, Z. Galil, and G.F. Italiano.
  Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
  Algorithms and Theoretical Computing Handbook, M. J. Atallah, ed., CRC Press, 1999, chapter 8.
  2nd. ed., CRC Press, 2010, Vol. I: General Concepts and Techniques, chapter 9, pp. 9–1 - 9-28.
  
• Approximate weighted farthest neighbors and minimum dilation stars.
  J. Augustine, D. Eppstein, and K. Wortman.
  arXiv:cs.CG/0602029.
  Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam.
  Springer, Lecture Notes in Comp. Sci. 6196, 2010, pp. 90–99.
  Discrete Mathematics, Algorithms and Applications 2 (4): 553–565, 2010.

  The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space. This leads to fast approximation algorithms for the constrained minimum dilation star problem in any fixed dimension.

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

• Linear-time algorithms for geometric graphs with sublinearly many crossings.
  D. Eppstein, M. T. Goodrich, and D. Strash.
  arXiv:0812.0893.
  20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 150–159.
  SIAM J. Computing 39 (8): 3814–3829, 2010.

  If a connected graph corresponds to a set of points and line segments in the plane, in such a way that the number of crossing pairs of line segments is sublinear in the size of the graph by an iterated-log factor, then we can find the arrangement of the segments in linear time. It was previously known how to find the arrangement in linear time when the number of crossings is superlinear by an iterated-log factor, so the only remaining open case is when the number of crossings is close to the size of the graph.

• Planar Voronoi diagrams for sums of convex functions, smoothed distance and dilation.
  M. Dickerson, D. Eppstein, and K. Wortman.
  arXiv:0812.0607.
  7th Int. Symp. Voronoi Diagrams in Science and Engineering (ISVD 2010), Quebec City, Canada, pp. 13–22.

  Investigates Voronoi diagrams for a "smoothed distance" in which the distance between two points p and q is inversely weighted by the perimeter of triangle opq for a fixed point o, its relation to dilation of star networks centered at o, and its generalization to minimization diagrams of certain convex functions. When the function to be minimized is suitably well-behaved, its level sets form pseudocircles, the bisectors of the minimization diagram form pseudoline arrangements, and the diagram itself has linear complexity.

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

• Paired approximation problems and incompatible inapproximabilities.
  D. Eppstein.
  arXiv:0909.1870.
  21st ACM-SIAM Symp. Discrete Algorithms, Austin, Texas, 2010, pp. 1076–1086.

  Considers situations in which two hard approximation problems are presented by means of a single input. In many cases it is possible to guarantee that one or the other problem can be approximated to within a better approximation ratio than is possible for approximating it as a single problem. For instance, it is possible to find either a (1+ε)-approximation to a 1-2 TSP defined from a graph or a n^ε-approximation to the maximum independent set of the same graph, despite lower bounds showing nonexistence of approximation schemes for 1-2 TSP and nonexistence of approximations better than n^1 − ε for independent set. However, for some other pairs of problems, such as hitting set and set cover, we show that solving the paired problem approximately is no easier than solving either problem independently.

  (Slides)

• Growth and decay in life-like cellular automata.
  D. Eppstein.
  arXiv:0911.2890.
  Game of Life Cellular Automata (Andrew Adamatzky, ed.), Springer, 2010, pp. 71–98.

  We classify semi-totalistic cellular automaton rules according to whether patterns can escape any finite bounding box and whether patterns can die out completely, with the aim of finding rules with interesting behavior similar to Conway's Game of Life. We survey a number of such rules.

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

  (Slides)

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

• Cloning Voronoi diagrams via retroactive data structures.
  M. Dickerson, D. Eppstein, and M. T. Goodrich.
  arXiv:1006.1921.
  18th Eur. Symp. Algorithms, Liverpool, 2010.
  Springer, Lecture Notes in Comp. Sci. 6346, 2010, pp. 362–373.
  

  We analyze the security of an online geometric database that allows planar nearest-neighbor queries but that does not wish the entire database to be copied by a competitor. We show that, under several models of how the query answers are returned, the database can be copied in a linear or near-linear number of queries. Our method for the competitor to copy the database is based on simulating Fortune's sweep-line algorithm for Voronoi diagrams, backtracking when the simulation discovers the existence of another point that invalidates earlier parts of the Voronoi diagram construction, and using retroactive data structures to perform the backtracking steps efficiently.

• Regular labelings and geometric structures.
  D. Eppstein.
  arXiv:1007.0221.
  Invited to 22nd Canadian Conference on Computational Geometry (CCCG 2010).
  Invited to Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, p. 1.
  

  We survey regular labelings for straight-line embedding of planar graphs on grids, rectangular partitions, and orthogonal polyhedra, and the many similarities between these different types of labeling.

  (CCCG talk slides)

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

• Listing all maximal cliques in sparse graphs in near-optimal time.
  D. Eppstein, M. Löffler, and D. Strash.
  arXiv:1006.5440.
  Workshop on Exact Algorithms for NP-Hard Problems, Dagstuhl, Germany, 2010.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 403–414.
  

  We describe an algorithm for finding all maximal cliques in a graph, in time O(dn3^d/3) where n is the number of vertices and d is the degeneracy of the graph, a standard measure of its sparsity. This time bound matches the worst-case output size for these parameters. The algorithm modifies the Bron-Kerbosch algorithm for maximal cliques by ordering the vertices by degree in the outer recursive call of the algorithm.

  For the journal version, see "Listing all maximal cliques in large sparse real-world graphs," which combines results from this and a different conference paper.

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

• Lombardi drawings of graphs.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 195–207.
  arXiv:1009.0579.
  Invited talk at 7th Dutch Computational Geometry Day, Eindhoven, the Netherlands, 2010.
  J. Graph Algorithms and Applications 16 (1): 85–108, 2012 (special issue for GD 2010).

  In honor of artist Mark Lombardi, we define a Lombardi drawing to be a drawing of a graph in which the edges are drawn as circular arcs and at each vertex they are equally spaced around the vertex so as to achieve the best possible angular resolution. We describe algorithms for constructing Lombardi drawings of regular graphs, 2-degenerate graphs, graphs with rotational symmetry, and several types of planar graphs. A program for the rotationally symmetric case, the Lombardi Spirograph, is available online.

• Optimal 3D angular resolution for low-degree graphs.
  D. Eppstein, M. Löffler, E. Mumford, and M. Nöllenburg.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 208–219.
  arXiv:1009.0045.
  J. Graph Algorithms and Applications 17 (3): 173–200, 2013.

  We show how to draw any graph of maximum degree three in three dimensions with 120 degree angles at each vertex or bend, and any graph of maximum degree four in three dimensions with the angles of the diamond lattice at each vertex or bend. In each case there are no crossings and the number of bends per edge is a small constant.

• Extended dynamic subgraph statistics using h-index parameterized data structures.
  D. Eppstein, M. T. Goodrich, D. Strash, and L. Trott.
  Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Hawaii, 2010.
  Springer, Lecture Notes in Comp. Sci. 6508, 2010, pp. 128–141.
  arXiv:1009.0783.
  Theor. Comput. Sci. 447: 44–52, 2012 (special issue for COCOA 2010).

  An earlier paper with Spiro at WADS 2009 provided dynamic graph algorithms for counting how many copies of each possible type of subgraph there are in a larger undirected graph, when the subgraphs have at most three vertices. This paper extends the method to directed graphs and to larger numbers of vertices per subgraph.

• Privacy-preserving data-oblivious geometric algorithms for geographic data.
  D. Eppstein, M. T. Goodrich, and R. Tamassia.
  Proc. 18th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS 2010), San Jose, California, pp. 13–22.
  arXiv:1009.1904.

  An algorithm is data-oblivious if the memory access patterns it makes depend only on the input size and not on the actual input values; data-oblivious algorithms are an important building block of cryptographic protocols that allow algorithmic tasks to be solved by parties who each have some subset of the input data that they do not wish to reveal. We show how to solve several basic geometric problems data-obliviously, including construction of convex hulls, quadtrees, and well-separated pair decompositions, and computation of closest pairs and all nearest neighbors.

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