David Eppstein - Publications

Publications with Joe Simons

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

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

• Set-difference range queries.
  D. Eppstein, M. T. Goodrich, and J. Simons.
  arXiv:1306.3482.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.

  We show how to use invertible Bloom filters as part of range searching data structures that determine the differences between the members of two sets that lie in a given query range.

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