David Eppstein - Publications

Publications with Michael J. Bannister

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

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

• Inapproximability of orthogonal compaction.
  M. J. Bannister, D. Eppstein, and J. Simons.
  arXiv:1108.4705.
  J. Graph Algorithms and Applications 16 (3): 651–673, 2012. (Special issue for GD 2011.)

  This is the journal version of "Hardness of approximate compaction for nonplanar orthogonal graph drawings". It has stronger inapproximability bounds, and more variations of the compaction problem that are hard to approximate. In addition it includes a retraction of a buggy approximation algorithm from the conference version.

• Force-directed graph drawing using social gravity and scaling.
  M. J. Bannister, D. Eppstein, M. T. Goodrich, and L. Trott.
  arXiv:1209.0748.
  20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
  Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 414–425.
  

  We extend force-directed methods of graph drawing by adding a force that pulls vertices towards the center of the drawing, with a strength proportional to the centrality of the vertex. Gradually scaling up this force helps avoid the tangling that would otherwise result from its use.

• Windows into relational events: data structures for contiguous subsequences of edges.
  M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth.
  NIPS 2012 Workshop on Algorithmic and Statistical Approaches for Large Social Networks, South Lake Tahoe, California, 2012 (poster and invited talk).
  24th ACM-SIAM Symp. Discrete Algorithms, New Orleans, Louisiana, 2013, pp. 856–864.
  arXiv:1209.5791.

  We study relational event data in which a collection of actors in a social network have a sequence of pairwise interactions. Contiguous subsequences of these interactions form graphs, and we develop efficient data structures for querying the parameters of these graphs.

• Parameterized complexity of 1-planarity.
  M. J. Bannister, S. Cabello, and D. Eppstein.
  arXiv:1304.5591.
  13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 97–108.
  J. Graph Algorithms and Applications 22 (1): 23–49, 2018. (Special issue on Graph Drawing Beyond Planarity.)
  

  We show that testing whether a graph is 1-planar (drawable with at most one crossing per edge) may be performed in polynomial and fixed-parameter tractable time for graphs of bounded circuit rank, vertex cover number, or tree-depth. However, it is NP-complete for graphs of bounded treewidth, pathwidth, or bandwidth.

  (Slides)

• Fixed parameter tractability of crossing minimization of almost-trees.
  M. J. Bannister, D. Eppstein, and J. Simons.
  arXiv:1308.5741.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 340–351.
  

  Many real-world graphs are k-almost-trees for small values of k: graphs in which, in every biconnected component, removing a spanning tree leaves at most k edges. We use kernelization methods to show that in such graphs, the 1-page and 2-page crossing numbers can be computed quickly.

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

• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth.
  M. J. Bannister and D. Eppstein.
  arXiv:1408.6321.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 210–221.
  J. Graph Algorithms & Applications 22 (4): 577–606, 2018.

  We show how to express in monadic second-order logic the problems of drawing a graph with a fixed number of crossings on a one or two page book layout. By applying Courcelle's theorem, we obtain fixed-parameter tractable algorithms for these problems, parameterized by treewidth.

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

• Confluent orthogonal drawings of syntax diagrams.
  M. J. Bannister, D. A. Brown, and D. Eppstein.
  arXiv:1509.00818.
  23rd Int. Symp. Graph Drawing, Los Angeles, California, 2015.
  Springer, Lecture Notes in Comp. Sci. 9411 (2015), pp. 260–271.

  We describe a system for transforming context-free grammars into human-readable syntax diagrams, including optimizations that change the structure of the grammar to make it more readable without affecting the language described by the grammar.