David Eppstein - Publications

2011

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

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

• Succinct greedy geometric routing using hyperbolic geometry.
  D. Eppstein and M. T. Goodrich.
  arXiv:0806.0341.
  Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008
  (under the different title "Succinct greedy graph drawing in the hyperbolic plane"),
  Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 14–25.
  IEEE Transactions on Computing 60 (11): 1571–1580, 2011.

  Greedy drawing is an idea for encoding network routing tables into the geometric coordinates of an embedding of the network, but most previous work in this area has ignored the space complexity of these encoded tables. We refine a method of R. Kleinberg for embedding arbitrary graphs into the hyperbolic plane, which uses linearly many bits to represent each vertex, and show that only logarithmic bits per point are needed.

• The Fibonacci dimension of a graph.
  S. Cabello, D. Eppstein, and S. Klavžar.
  IMFM Preprint 1084, Institute of Mathematics, Physics and Mechanics, Univ. of of Ljubljana, 2009.
  arXiv:0903.2507.
  Electronic J. Combinatorics 18(1), Paper P55, 2011.

  We investigate isometric embeddings of other graphs into Fibonacci cubes, graphs formed from the families of fixed-length bitstrings with no two consecutive ones.

• Optimal angular resolution for face-symmetric drawings.
  D. Eppstein and K. Wortman.
  arXiv:0907.5474.
  J. Graph Algorithms and Applications 15 (4): 551–564, 2011.

  We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.

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

• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension.
  D. Eppstein and M. Löffler.
  Proc. 27th ACM Symp. on Computational Geometry, Paris, 2011, pp. 361–368.
  arXiv:1103.2575.
  Discrete Comput. Geom. 50 (1): 1–21, 2013.

  Suppose that P is the intersection of n halfspaces in D dimensions, but that the bounded faces of P are at most d-dimensional, for some d that is much smaller than D. Then in this case we show that the number of vertices of P is O(n^d), independent of D. We also investigate related bounds on the number of bounded faces of all dimensions of P, and algorithms for efficiently listing the vertices and bounded faces of P.

• On 2-site Voronoi diagrams under geometric distance functions.
  G. Barequet, M. Dickerson, D. Eppstein, D. Hodorkovsky, and K. Vyatkina.
  27th Eur. Worksh. Comp. Geom., Antoniushaus Morschach, Switzerland, 2011, pp. 59–62.
  Proc. 8th Int. Symp. Voronoi Diagrams in Science and Engineering, Qing Dao, China, 2011, pp. 31–38.
  arXiv:1105.4130.
  J. Computer Science and Technology 28 (2): 267–277, 2013.

  We study the combinatorial complexity of generalized Voronoi diagrams that determine the closest two point sites to a query point, where the distance from the query point to a pair of sites is a combination of the individual distances to the sites and the distance from one site in the pair to the other.

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein and D. Strash.
  10th Int. Symp. Experimental Algorithms, Crete, 2011.
  Springer, Lecture Notes in Comp. Sci. 6630, 2011, pp. 364–375.
  arXiv:1103.0318.

  We experiment with our degeneracy-based algorithm for listing maximal cliques in sparse graphs and show that it works well on large graphs drawn from several repositories of real-world social networks and bioinformatics networks.

  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.

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

• Tracking moving objects with few handovers.
  D. Eppstein, M. T. Goodrich, and M. Löffler.
  arXiv:1105.0392.
  12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011.
  Springer, Lecture Notes in Comp. Sci. 6844, 2011, pp. 362–373.

  We apply competitive analysis to the problem of deciding online which cell phone tower to change to when a phone moves out of the coverage region of the tower it is connected to. We show that, when the coverage regions have constant ply (at most a constant number of them overlap any point of the plane) it is possible to get within a constant factor of the minimum possible number of handovers that an offline algorithm could achieve.

• What's the difference? Efficient set reconciliation without prior context.
  D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese.
  Proc. ACM SIGCOMM, Toronto, Canada, 2011.

  We determine the symmetric difference between two similar sets of items, held by different machines on the internet, using an amount of communication bandwidth that is proportional only to the difference between the sets and with low computational overhead. Our solution technique combines the invertible Bloom filter data structure from our previous work on streaming straggler detection with a randomized sampling scheme that allows us to accurately and efficiently estimate the size of the difference.

• Category-based routing in social networks: membership dimension and the small-world phenomenon.
  D. Eppstein, M. T. Goodrich, M. Löffler, D. Strash, and L. Trott.
  Workshop on Graph Algorithms and Applications, Zürich, Switzerland, July 2011.
  International Conference on Computational Aspects of Social Networks (CASoN 2011), Salamanca, Spain, October 2011.
  arXiv:1108.4675.
  Theor. Comput. Sci. 514: 96–104, 2013. (Special issue on Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello)
  

  We investigate greedy routing schemes for social networks, in which participants know categorical information about some other participants and use it to guide message delivery by forwarding messages to neighbors that have more categories in common with the eventual destination. We define the membership dimension of such a scheme to be the maximum number of categories that any individual belongs to, a natural measure of the cognitive load of greedy routing on its participants. And we show that membership dimension is closely related to the small world phenomenon: a social network can be given a category system with polylogarithmic membership dimension that supports greedy routing if, and only if, the network has polylogarithmic diameter.

• Confluent Hasse diagrams.
  D. Eppstein and J. Simons.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 2–13.
  arXiv:1108.5361.
  J. Graph Algorithms and Applications 17 (7): 689–710, 2013.

  We show that a partial order has a non-crossing upward planar drawing if and only if it has order dimension two, and we use the Dedekind-MacNeille completion to find a drawing with the minimum possible number of confluent junctions.

• Hardness of approximate compaction for nonplanar orthogonal graph drawings.
  M. J. Bannister and D. Eppstein.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 367–378.

  We show that, for several variants of the problem of compacting a grid drawing of a graph to use the minimum number of rows or minimum area, no good approximation algorithm is possible. We also develop fixed-parameter tractable algorithms and approximation algorithms showing that some of our inapproximability bounds are tight. See the journal version, "Inapproximability of orthogonal compaction", for some improvements and corrections.

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

• Randomized speedup of the Bellman–Ford algorithm.
  M. J. Bannister and D. Eppstein.
  arXiv:1111.5414.
  Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan, 2012, pp. 41–47.

  The Bellman–Ford algorithm for single-source shortest paths in graphs that may have negatively weighted edges but no negative cycles can be sped up by a technique of Yen in which the graph is partitioned into two directed acyclic subgraphs and edge relaxations alternate between these two subgraphs. We show that choosing this partition randomly gains an additional factor of 2/3 in running time.

• Privacy-enhanced methods for comparing compressed DNA sequences.
  D. Eppstein, M. T. Goodrich, and P. Baldi.
  arXiv:1107.3593.