David Eppstein - Publications

2007

• The traveling salesman problem for cubic graphs.
  D. Eppstein.
  arXiv:cs.DS/0302030.
  8th Worksh. Algorithms and Data Structures, Ottawa, 2003.
  Springer, Lecture Notes in Comp. Sci. 2748, 2003, pp. 307–318.
  J. Graph Algorithms and Applications 11 (1): 61–81, 2007.

  We find improved exponential-time algorithms for exact solution of the traveling salesman problem on graphs of maximum degree three and four. We also consider related problems including counting the number of Hamiltonian cycles in such graphs.

  (WADS 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.

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

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

• Improved combinatorial group testing for real-world problem sizes.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  9th Worksh. Algorithms and Data Structures, Waterloo, 2005.
  Springer, Lecture Notes in Comp. Sci. 3608, 2005, pp. 86–98.
  arXiv:cs.DS/0505048.
  SIAM J. Computing 36 (5): 1360–1375, 2007.

  We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.

  (Mike's WADS talk slides)

• Drawings of planar graphs with few slopes and segments.
  V. Dujmović, D. Eppstein, M. Suderman, and D. R. Wood.
  arXiv:math.CO/0606450.
  Comp. Geom. Theory & Applications 38: 194–212, 2007.

  We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface).

• Guard placement for efficient point-in-polygon proofs.
  D. Eppstein, M. T. Goodrich, and N. Sitchinava.
  arXiv:cs.CG/0603057.
  23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 27–36.

  The problem is to place as few wedges as possible in the plane such that a desired polygon can be formed as some monotone Boolean combination of the wedges. The motivation is for wireless devices to prove that they are located within a target area by their ability to communicate with a subset of base stations (the wedges). We provide upper and lower bounds on the number of wedges needed for several classes of polygons.

• Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition.
  D. Eppstein.
  arXiv:cs.CG/0604034.
  18th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2007, pp. 29–38.
  ACM Trans. Algorithms 5(3): Article 29, 2009.

  We find efficient constant factor approximation algorithms for hierarchically clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can also be used to provide a pants decomposition with approximately minimum total length.

  (Slides)

• Interconnect criticality driven delay relaxation.
  L. Singhal, E. Bozorgzadeh, and D. Eppstein.
  IEEE Trans. CAD 26 (10): 1803–1817, 2007.

  We consider a problem of assigning delays to components in a circuit so that each component is part of a critical path, but the number of edges belonging to critical paths is minimized. We show the problem to be NP-complete via a reduction from finding independent dominating sets in bipartite graphs minimizing dominated edges, and give experimental results on heuristics.

• Upright-quad drawing of \(st\)-planar learning spaces.
  D. Eppstein.
  arXiv:cs.CG/0607094.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 282–293.
  J. Graph Algorithms and Applications 12 (1): 51–72, 2008 (special issue for GD'06).

  We consider graph drawing algorithms for learning spaces, a type of \(st\)-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any \(st\)-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an \(st\)-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.

  (GD'06 talk slides)

• Trees with convex faces and optimal angles.
  J. Carlson and D. Eppstein.
  arXiv:cs.CG/0607113.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 77–88.

  We consider drawings of trees which, if the leaf edges were extended to infinite rays, would form partitions of the plane into unbounded convex polygons. For such a drawing the edges may be chosen independently without any possibility of edge crossing. We show how to choose the angles of such drawings to optimize the angular resolution of the drawing.

  (GD06 talk slides)

• Choosing colors for geometric graphs via color space embeddings.
  M. Dillencourt, D. Eppstein, and M. T. Goodrich.
  arXiv:cs.CG/0609033.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 294–305.

  We show how to choose colors for the vertices of a graph drawing in such a way that all colors are easily distinguishable, but such that adjacent vertices have especially dissimilar colors, by considering the problem as one of embedding the graph into a three-dimensional color space.

  (GD'06 talk slides)

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

• Edges and switches, tunnels and bridges.
  D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
  23rd European Workshop on Computational Geometry (EWCG'07), Graz, 2007.
  10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
  Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 77–88.
  Tech. Rep. UU-CS-2007-042, Utrecht Univ., Dept. of Information and Computing Sciences, 2007.
  arXiv:0705.0413.
  Comp. Geom. Theory & Applications 42 (8): 790–802, 2009 (special issue for EWCG'07).

  We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.

  (WADS talk slides)

• Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters.
  D. Eppstein, and M. T. Goodrich.
  10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
  Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 637–648.
  arXiv:0704.3313.
  IEEE Trans. Knowledge and Data Engineering 23 (2): 297–306, 2011.

  We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.

  (WADS talk slides)

• On verifying and engineering the well-gradedness of a union-closed family.
  D. Eppstein, J.-C. Falmagne, and H. Uzun.
  arXiv:0704.2919.
  38th Meeting of the European Mathematical Psychology Group, Luxembourg, 2007.
  J. Mathematical Psychology 53 (1): 34–39, 2009.

  We describe tests for whether the union-closure of a set family is well-graded, and algorithms for finding a minimal well-graded union-closed superfamily of a given set family.

• Recognizing partial cubes in quadratic time.
  D. Eppstein.
  arXiv:0705.1025.
  19th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 2008, pp. 1258–1266.
  J. Graph Algorithms and Applications 15 (2): 269–293, 2011.

  We show how to test whether a graph is a partial cube, and if so embed it isometrically into a hypercube, in time O(n²), improving previous O(nm)-time solutions; here n is the number of vertices and m is the number of edges. The ideas are to use bit-parallelism to speed up previous approaches to the embedding step, and to verify that the resulting embedding is isometric using an all-pairs shortest path algorithm from "algorithms for media".

  (slides)

• Geometry of partial cubes.
  D. Eppstein.
  Invited talk at 6th Slovenian International Conference on Graph Theory, Bled, Slovenia, 2007.

  I survey some of my recent results on geometry of partial cubes, including lattice dimension, graph drawing, cubic partial cubes, and partial cube flip graphs of triangulations.

  (Slides)

• The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing.
  D. Eppstein.
  arXiv:0709.4087.
  Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
  Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 78–89.
  J. Graph Algorithms and Applications 17 (1): 35–55, 2013.

  Defines a class of orthogonal graph drawings formed by a point set in three dimensions for which axis-parallel line contains zero or two vertices, with edges connecting pairs of points on each nonempty axis-parallel line. Shows that the existence of such a drawing can be defined topologically, in terms of certain two-dimensional surface embeddings of the same graph. Based on this equivalence, describes algorithms, graph-theoretic properties, and hardness results for graphs of this type.

  (Slides from talk at U. Arizona, February 2008 – Slides from GD08) )

• Media Theory: Interdisciplinary Applied Mathematics.
  D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov.
  Springer, 2007, ISBN 978-3-540-71696-9.

  Many combinatorial structures such as the set of acyclic orientations of a graph, weak orderings of a set of elements, or chambers of a hyperplane arrangement have the structure of a partial cube, a graph in which vertices may be labeled by bitvectors in such a way that graph distance equals Hamming distance. This book analyzes these structures in terms of operations that change one vertex to another by flipping a single bit of the bitvector labelings. It incorporates material from several of my papers including "Algorithms for Media", "Algorithms for Drawing Media", "Upright-Quad Drawing of st-Planar Learning Spaces", and "The Lattice Dimension of a Graph".

  (Publisher's web site – Reinhard Suck's review in J. Math. Psych. – Reinhard Suck's review in MathSciNet)