David Eppstein - Publications

2016

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

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

• Convex-arc drawings of pseudolines.
  D. Eppstein, M. van Garderen, B. Speckmann, and T. Ueckerdt.
  21st Int. Symp. Graph Drawing (poster), Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 522–523.
  arXiv:1601.06865.
  

  We show that every outerplanar weak pseudoline arrangement (a collection of curves topologically equivalent to lines, each crossing at most once but possibly zero times, with all crossings belonging to an infinite face) can be straightened to a hyperbolic line arrangement. As a consequence such an arrangement can also be drawn in the Euclidean plane with each pseudoline represented as a convex piecewise-linear curve with at most two bends. In contrast, for arbitrary pseudoline arrangements, a linear number of bends is sufficient and sometimes necessary.

• Distance-sensitive point location made easy.
  B. Aronov, M. De Berg, D. Eppstein, M. Roeloffzen, and B. Speckmann.
  30th European Workshop on Computational Geometry (EuroCG 2014), Dead Sea, Israel, March 2014.
  arXiv:1602.00767
  Comp. Geom. Theory & Applications 54: 17–31, 2016.

  We use quadtrees to handle point location queries in an amount of time that depends on the distance of the query point to the nearest region boundary.

• Folding a paper strip to minimize thickness.
  E. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno.
  arXiv:1411.6371.
  9th International Workshop on Algorithms and Computation (WALCOM 2015), Dhaka, Bangladesh.
  Springer, Lecture Notes in Comp. Sci. 8973 (2015), pp. 113–124.
  Journal of Discrete Algorithms 36: 18–26, 2016 (special issue for WALCOM).
  

  If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.

• All-pairs minimum cuts in near-linear time for surface-embedded graphs.
  G. Borradaile, D. Eppstein, A. Nayyeri, and C. Wulff-Nilsen.
  arXiv:1411.7055.
  Proc. 32nd Int. Symp. Computational Geometry, Boston, 2016.
  Leibniz International Proceedings in Informatics (LIPIcs) 51, pp. 22:1–22:16.
  

  We give the first known near-linear algorithms for constructing Gomory–Hu trees of bounded-genus graphs, and we shave a log off the time for the same problem on planar graphs.

• Simple recognition of Halin graphs and their generalizations.
  D. Eppstein.
  arXiv:1502.05334.
  J. Graph Algorithms & Applications 20 (2): 323–346, 2016.

  We describe and implement a simple linear time algorithm for recognizing Halin graphs based on two simplifications of triples of degree-three vertices in such graphs. Removing some auxiliary data from the algorithm causes it to recognize a broader class of graphs that we call the D3-reducible graphs. We study the properties of these graphs, showing that they share many properties with the Halin graphs.

• Track layouts, layered path decompositions, and leveled planarity.
  M. J. Bannister, W. E. Devanny, and V. Dujmović, D. Eppstein, and D. R. Wood.
  arXiv:1506.09145.
  24th Int. Symp. Graph Drawing, Athens, Greece, 2016.
  Springer, Lecture Notes in Comp. Sci. 9801 (2016), pp. 499–510.
  Algorithmica 81 (4): 1561–1583, 2019.

  We introduce the concept of a layered path decomposition, and show that the layered pathwidth can be used to characterize the leveled planar graphs. As a consequence we show that finding the minimum number of tracks in a track layout of a given graph is NP-complete. The GD version includes only the parts concerning track layout, and uses the title "Track Layout is Hard".

• Rigid origami vertices: Conditions and forcing sets.
  Z. Abel, J. Cantarella, E. Demaine, D. Eppstein, T. Hull, J. Ku, R. Lang, and T. Tachi.
  arXiv:1507.01644.
  J. Computational Geometry 7 (1): 171–184, 2016.

  We give an exact characterization of the one-vertex origami folding patterns that can be folded rigidly, without bending the parts of the paper between the folds.

• Treetopes and their graphs.
  D. Eppstein.
  arXiv:1510.03152.
  27th ACM-SIAM Symp. on Discrete Algorithms, Arlington, 2016, pp. 969–984.
  Discrete Comput. Geom. 64 (2), 259–289, 2020 (special issue for Branko Grünbaum).
  

  We describe a class of polytopes of varying dimensions, whose restriction to three dimensions is the class of roofless polyhedra (Halin graphs). We call these polytopes treetopes. We show that the four-dimensional treetopes are closely related to clustered planar graph drawings, and we use this connection to recognize the graphs of four-dimensional treetopes in polynomial time.

  (Slides)

• On the planar split thickness of graphs.
  D. Eppstein, P. Kindermann, S. G. Kobourov, G. Liotta, A. Lubiw, A. Maignan, D. Mondal, H. Vosoughpour, S. Whitesides, and S. Wismath.
  arXiv:1512.04839.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 403–415.
  Algorithmica 80 (3): 977–994 (special issue for LATIN), 2018.

  We study the problem of splitting the vertices of a given graph into a bounded number of sub-vertices (with each edge attaching to one of the sub-vertices) in order to make the resulting graph planar. It is NP-complete, but can be approximated to within a constant factor, and is fixed-parameter tractable in the treewidth.

  (Slides)

• From discrepancy to majority.
  D. Eppstein and D. S. Hirschberg.
  arXiv:1512.06488.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 390–402.
  Algorithmica 80 (4): 1278–1297, 2018.

  We provide upper and lower bounds on the query complexity of a problem in which the input is a collection of two-colored items, and the problem is to either find an item of the majority color or to determine that there is no majority, by performing queries that determine the discrepancy of fixed-size subsets of the items.

  (Slides)

• Cuckoo filter: simplification and analysis.
  D. Eppstein.
  arXiv:1604.06067.
  Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland.
  Leibniz International Proceedings in Informatics (LIPIcs) 53, pp. 8.1–8.12.

  A cuckoo filter is an approximate set data structure that can be used in place of a Bloom filter, but with several practical advantages: it uses less space, has better locality of reference, and can handle element deletions. We provide the first theoretical analysis of a simplified variation of cuckoo filters, showing that these advantages can be guaranteed to hold theoretically and not just experimentally.

  (Slides)

• The computational hardness of dK-series.
  W. E. Devanny, D. Eppstein, and B. Tillman.
  NetSci2016 poster session, Seoul, Korea.

  The dK-series is an extension of the degree sequence of a graph to a d-dimensional tensor, describing the number of d-tuples of vertices with each possible combination of degrees and adjacencies. As we show, it is NP-hard to determine whether such a tensor represents a valid graph, for any d ≥ 3, or for d = 2 if the number of triangles in the graph is also specified (or constrained to be zero).

• Models and algorithms for graph watermarking.
  D. Eppstein, M. T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, and M. Torres.
  arXiv:1605.09425.
  Proc. 19th Information Security Conference (ISC 2016), Honolulu, Hawaii.
  Springer, Lecture Notes in Comp. Sci. 9866 (2016), pp. 283–301.

  We show how to modify a small number of edges in a large social network in order to make the modified copy easy to identify, even if an adversary tries to hide the modification by permuting the vertices and flipping a much larger number of edges. The result depends on the random fluctuation of vertex degrees in such networks, and the ability to uniquely identify vertices by their adjacencies to a small number of high-degree landmark vertices. This paper won the best student paper award at ISC for its student co-authors Lam, Mamano, and Torres.

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

• Scheduling autonomous vehicle platoons through an unregulated intersection.
  J. Besa, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
  Proc. 16th Worksh. Algorithmic Approaches for Transportation Modelling, Optimization and Systems (ATMOS 2016), Aarhus, Denmark, 2016.
  OpenAccess Series in Informatics (OASIcs) 54, Schloss Dagstuhl (2016), pp. 5:1–5.16.
  arXiv:1609.04512.
  

  We consider a model of vehicle scheduling in which vehicles arrive at an intersection in indivisible platoons (or individual vehicles of variable length) and the goal is to find a schedule for them to all cross the intersection without collisions, minimizing the maximimum delay incurred by any platoon. We show that for many types of intersections, an optimal schedule can be found in polynomial time by a combination of dynamic programming and parametric search.

• Spanning trees in multipartite geometric graphs.
  A. Biniaz, P. Bose, D. Eppstein, A. Maheshwari, P. Morin, and M. Smid.
  arXiv:1611.01661.
  Algorithmica 80 (11): 3177–3191, 2018.

  We provide near-linear-time algorithms for minimum and maximum spanning trees on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance.

• Covering many points with a small-area box.
  M. De Berg, S. Cabello, O. Cheong, D. Eppstein, and C. Knauer.
  arXiv:1612.02149.
  J. Computational Geometry 10 (1): 207–222, 2019.
  

  We give an efficient algorithm for finding the smallest axis-parallel rectangle covering a given number of points out of a larger set of points in the plane.

• Maximum plane trees in multipartite geometric graphs.
  A. Biniaz, P. Bose, J.-L. De Carufel, K. Crosbie, D. Eppstein, A. Maheshwari, M. Smid.
  15th Algorithms and Data Structures Symp. (WADS 2017), St. John's, Newfoundland.
  Springer, Lecture Notes in Comp. Sci. (2017), pp. 193–204.
  Algorithmica 81 (4): 1512–1534, 2019.

  We consider problems of constructing the maximum-length plane (non-self-crossing) spanning tree on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance. We show that several such problems can be efficiently approximated.