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.
  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
  Journal of 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.
  Lecture Notes in Computer Science 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, to appear.

  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.

Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.