David Eppstein – Publications

Publications with Bettina Speckmann

• Edges and switches, tunnels and bridges.
  D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
  23rd European Workshop on Computational Geometry (EWCG'07), Graz, 2007.
  10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
  Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 77–88.
  Tech. Rep. UU-CS-2007-042, Utrecht Univ., Dept. of Information and Computing Sciences, 2007.
  arXiv:0705.0413.
  Comp. Geom. Theory & Applications 42 (8): 790–802, 2009 (special issue for EWCG'07).

  We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.

  (WADS talk slides)

• Area-universal rectangular layouts.
  D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
  arXiv:0901.3924.
  25th Eur. Worksh. Comp. Geom., Brussels, Belgium, 2009.
  25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, pp. 267–276.

  A partition of a rectangle into smaller rectangles is "area-universal" if any vector of areas for the smaller rectangles can be realized by a combinatorially equivalent partition. These partitions may be applied, for instance, to cartograms, stylized maps in which the shapes of countries have been distorted so that their areas represent numeric data about the countries. We characterize area-universal layouts, describe algorithms for finding them, and discuss related problems. The algorithms for constructing area-universal layouts are based on the distributive lattice structure of the set of all layouts of a given dual graph.

  Merged with "Orientation-constrained rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".

  (SoCG talk slides)

• Improved grid map layout by point set matching.
  D. Eppstein, M. van Kreveld, B. Speckmann, and F. Staals.
  28th European Workshop on Computational Geometry (EuroCG'12), Assisi, Italy, 2012.
  6th IEEE Pacific Visualization Conf. (PacificVis), Sydney, Australia, 2013.
  Int. J. Comput. Geom. Appl. 25 (2): 101–122, 2015.

  We study the problem of matching geographic regions to points in a regular grid, minimizing the distance between each region's centroid and the corresponding grid point, and preserving as much as possible the relative orientations between pairs of regions.

• Area-universal and constrained rectangular layouts.
  D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
  SIAM J. Computing 41 (3): 537–564, 2012.

  A combined journal version of "Area-universal rectangular layouts" and "Orientation-constrained rectangular layouts".

  (Local copy of article)

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