David Eppstein - Publications

Publications with William E. Devanny

• Superpatterns and universal point sets.
  M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein.
  arXiv:1308.0403.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 208–219.
  Bannister's talk on this paper won the GD2013 best presentation award.
  J. Graph Algorithms & Applications 18 (2): 177–209, 2014 (special issue for GD'13).

  A superpattern of a set of permutations is a permutation that contains as a pattern every permutation in the set. Previously superpatterns had been considered for all permutations of a given length; we generalize this to sets of permutations defined by forbidden patterns; we show that the 213-avoiding permutations have superpatterns half the length of the known bound for all permutations, and that any proper permutation subclass of the 213-avoiding permutations has near-linear superpatterns. We apply these results to the construction of universal point sets, sets of points that can be used as the vertices of drawings of all n-vertex planar graphs. We use our 213-avoiding superpatterns to construct universal sets of size approximately \(n^2/4\), and we also construct near-linear universal sets for graphs of bounded pathwidth.

• Small superpatterns for dominance drawing.
  M. J. Bannister, W. E. Devanny, and D. Eppstein.
  arXiv:1310.3770.
  Analytic Algorithmics and Combinatorics (ANALCO14), Portland, Oregon, 2014, pp. 92–103.

  We construct small universal point sets for dominance drawings of classes of acyclic graphs, by finding forbidden patterns in the permutations determined by these drawings and proving the existence of small superpatterns for the permutations with these patterns forbidden. In particular, dominance drawings of the Hasse diagrams of width-2 partial orders have universal point sets of size O(n^3/2), derived from superpatterns of the same size for the 321-avoiding permutations, and dominance drawings of st-planar graphs have universal point sets of size O(n log n), derived from superpatterns for riffle shuffles.

• The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings.
  M. J. Bannister, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
  arXiv:1408.1422.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 149–161.
  J. Graph Algorithms & Applications 19 (2): 619–656, 2015 (special issue for GD'14).

  We show that many standard graph drawing methods have algebraic solutions described by polynomials that can have unsolvable Galois groups, and that can have Galois groups whose order is divisible by large prime numbers. As a consequence certain models of exact algebraic computation are unable to construct these drawings.

• ERGMs are hard.
  M. J. Bannister, W. E. Devanny, and D. Eppstein.
  arXiv:1412.1787.
  

  ERGMs (exponential random graph models) are used in social science to describe probability distributions on graphs that are supposed to mimic real-world social networks. However, we show that (with features that are standard in the social science application) the distributions given by these models can be computationally infeasible to sample from or to approximate the probability of seeing a given graph.

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

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

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

• Square-contact representations of partial 2-trees and triconnected simply-nested graphs.
  G. Da Lozzo, W. E. Devanny, D. Eppstein, and T. Johnson.
  arXiv:1710.00426.
  Proc. 28th Int. Symp. Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 2017.
  Leibniz International Proceedings in Informatics (LIPIcs) 92, pp. 24:1–24:16.
  

  We show that the K_1,1,3-free partial 2-trees and the Halin graphs other than K₄ can all be represented as proper contact graphs of squares in the plane. Among partial 2-trees and Halin graphs, these are exactly the ones that can be embedded without nonempty triangles, which form an obstacle to the existence of square contact representations. However the graph of a square antiprism has no such representation despite being embeddable without any nonempty triangles.

• Quadratic time algorithms appear to be optimal for sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 87–96.
  arXiv:1805.05443.

  We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.

• Optimally sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  arXiv:1805.03350
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 81:1–81:13.
  

  Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.