David Eppstein - Publications

2004

• Fast approximation of centrality.
  D. Eppstein and J. Wang.
  arXiv:cs.DS/0009005.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 228–229.
  J. Graph Algorithms & Applications 8 (1): 39–45, 2004.

  We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.

  (SODA paper)

• Separating thickness from geometric thickness.
  D. Eppstein.
  arXiv:math.CO/0204252.
  10th Int. Symp. Graph Drawing, Irvine, 2002.
  Springer, Lecture Notes in Comp. Sci. 2528, 2002, pp. 150–161.
  In Towards a Theory of Geometric Graphs, AMS, 2004, Contemporary Math 342, J. Pach, ed., pp. 75–86.

  We show that thickness and geometric thickness are not asymptotically equivalent: for every t, there exists a graph with thickness three and geometric thickness > t. The proof uses Ramsey-theoretic arguments similar to those in "Separating book thickness from thickness".

  (GD'02 talk slides)

• Confluent drawings: visualizing non-planar diagrams in a planar way.
  M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
  arXiv:cs.CG/0212046.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
  J. Graph Algorithms and Applications (special issue for GD'03) 9 (1): 31–52, 2005.

  We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.

• Tiling space and slabs with acute tetrahedra.
  D. Eppstein, J. M. Sullivan, and A. Üngör.
  arXiv:cs.CG/0302027.
  Comp. Geom. Theory & Applications 27 (3): 237–255, 2004.

  We show it is possible to triangulate three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08 degrees, and another which tiles a slab in space.

• Lazy algorithms for dynamic closest pair with arbitrary distance measures.
  J. Cardinal and D. Eppstein.
  Tech. Rep. 502, Univ. Libre de Bruxelles, Computer Science Dept., 2003.
  Worksh. Algorithm Engineering and Experiments (ALENEX), New Orleans, 2004, pp. 112–119.

  We modify my previous data structures for dynamic closest pairs, to use a lazy deletion mechanism, and show in experiments that the results are an improvement on the unmodified structures.

• Quasiconvex analysis of backtracking algorithms.
  D. Eppstein.
  arXiv:cs.DS/0304018.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 781–790.
  ACM Trans. Algorithms 2 (4): 492–509 (special issue for SODA 2004), 2006.

  We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.

  The journal version uses the longer title "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms".

  (SODA talk slides)

• Quasiconvex programming.
  D. Eppstein.
  Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
  Plenary talk at ALGO 2004, Bergen, Norway, 2004.
  arXiv:cs.CG/0412046.
  Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287–331.

  Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.

  (DIMACS talk slides – ALGO talk slides)

• Testing bipartiteness of geometric intersection graphs.
  D. Eppstein.
  arXiv:cs.CG/0307023.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 853–861.
  ACM Trans. Algorithms 5(2):15, 2009.

  We consider problems of partitioning sets of geometric objects into two subsets, such that no two objects within the same subset intersect each other. Typically, such problems can be solved in quadratic time by constructing the intersection graph and then applying a graph bipartiteness testing algorithm; we achieve subquadratic times for general objects, and O(n log n) times for balls in R^d or simple polygons in the plane, by using geometric data structures, separator based divide and conquer, and plane sweep techniques, respectively. We also contrast the complexity of bipartiteness testing with that of connectivity testing, and provide evidence that for some classes of object, connectivity is strictly harder due to a computational equivalence with Euclidean minimum spanning trees.

  (SODA talk slides)

• Deterministic sampling and range counting in geometric data streams.
  A. Bagchi, A. Chaudhary, D. Eppstein, and M. T. Goodrich.
  arXiv:cs.CG/0307027.
  20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 144–151.
  ACM Trans. Algorithms 3(2):A16, 2007.

  We describe an efficient streaming-model construction of epsilon-nets and epsilon-approximations, and use it to find deterministic streaming-model approximation algorithms for iceberg range queries and for various robust statistics problems.

• Selected open problems in graph drawing.
  F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 515–539.

  We survey a number of open problems in theoretical and applied graph drawing.

• The geometric thickness of low degree graphs.
  C. Duncan, D. Eppstein, and S. Kobourov.
  arXiv:cs.CG/0312056.
  20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 340–346.

  We show that graphs with maximum degree four have geometric thickness at most two, by partitioning them into degree two subgraphs and applying simultaneous embedding techniques.

• Single-strip triangulation of manifolds with arbitrary topology.
  D. Eppstein and M. Gopi.
  13th Video Review of Computational Geometry, 2004.
  20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 455–456 (abstract for video).
  25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics '04), Grenoble, 2004 (2nd best paper award).
  Eurographics Forum 23 (3): 371–379, 2004.
  arXiv:cs.CG/0405036.

  We describe a new algorithm, based on graph matching, for subdividing a triangle mesh (without boundary) so that it has a Hamiltonian cycle of triangles, and prove that this subdivision process increases the total number of triangles in the mesh by at most a factor of 3/2. We also prove lower bounds on the increase needed for meshes with and without boundary.

  (Graphics lab pubs page)

• The effect of faults on network expansion.
  A. Bagchi, A. Bhargava, A. Chaudhary, D. Eppstein, and C. Scheideler.
  arXiv:cs.DC/0404029.
  16th ACM Symp. Parallelism in Algorithms and Architectures, Barcelona, 2004, pp. 286–293.
  Theory of Computing Systems 39 (6): 903–928, 2006.

  Studies the resilience of distributed computation networks against adversarial and random fault models; shows that, in both models, certain networks can withstand constant fault probabilities and still contain a large subnetwork with similar expansion to the original.

• The lattice dimension of a graph.
  D. Eppstein.
  arXiv:cs.DS/0402028.
  Eur. J. Combinatorics 26 (6): 585–592, 2005.

  Describes a polynomial time algorithm for isometrically embedding graphs into an integer lattice of the smallest possible dimension. The technique involves maximum matching in an auxiliary graph derived from a partial cube representation of the input.

• Algorithms for drawing media.
  D. Eppstein.
  arXiv:cs.DS/0406020.
  12th Int. Symp. Graph Drawing, New York, 2004.
  Springer, Lecture Notes in Comp. Sci. 3383, 2004, pp. 173–183.

  We describe two algorithms for finding planar layouts of partial cubes: one based on finding the minimum-dimension lattice embedding of the graph and then projecting the lattice onto the plane, and the other based on representing the graph as the planar dual to a weak pseudoline arrangement.

  Due to editorial mishandling there will be no journal version of this paper: I submitted it to a journal in 2004, the reviews were supposedly sent back to me in 2005, but I didn't receive them and didn't respond to them, leading the editors to assume that I intended to withdraw the submission. Large portions of the paper have since been incorporated into my book Media Theory, making journal publication moot.

  (GD04 talk slides)

• Confluent layered drawings.
  D. Eppstein, M. T. Goodrich, and J. Meng.
  12th Int. Symp. Graph Drawing, New York, 2004.
  Springer, Lecture Notes in Comp. Sci. 3383, 2004, pp. 184–194.
  arXiv:cs.CG/0507051.
  Algorithmica 47 (4): 439–452 (special issue for Graph Drawing), 2007.

  Describes a graph drawing technique combining ideas of confluent drawing with Sugiyama-style layered drawing. Uses a reduction to graph coloring to find and visualize sets of bicliques in each layer.

• All maximal independent sets and dynamic dominance for sparse graphs.
  D. Eppstein.
  arXiv:cs.DS/0407036.
  16th ACM-SIAM Symp. Discrete Algorithms, Vancouver, 2005, pp. 451–459.
  ACM Trans. Algorithms 5(4):A38, 2009.

  We show how to apply reverse search to list all maximal independent sets in bounded-degree graphs in constant time per set, in graphs from minor closed families in linear time per set, and in sparse graphs in subquadratic time per set. The latter two results rely on new data structures for maintaining a dynamic vertex set in a graph and quickly testing whether the set dominates all other vertices.

  (SODA05 talk slides)

• Minimum dilation stars.
  D. Eppstein and K. Wortman.
  arXiv:cs.CG/0412025.
  21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 321–326.
  Comp. Geom. Theory & Applications 37 (1): 27–37, 2007.

  We show how to test the dilation of a star, embedded in a Euclidean space of bounded dimension, in time O(n log n), and how to find the star center that has the minimum dilation for a given set of leaf points in randomized expected time O(n log n). For two-dimensional points, we can find the minimum dilation center, constrained to be one of the input points, in time O(n 2^α(n) log²n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.

  (SoCG05 talk slides)

• Comment on "Location-Scale Depth".
  D. Eppstein.
  J. Amer. Stat. Assoc. 99 (468): 976–979, 2004.

  Discusses a paper by Mizera and Müller on depth-based methods for simultaneously fitting both a center and a radius to a set of sample points, by viewing the points as lying on the boundary of a model of a higher dimensional hyperbolic space. Reformulates their method in combinatorial terms more likely to be familiar to computational geometers, and discusses the algorithmic implications of their work.