David Eppstein – Publications

Publications with Kevin Verbeek

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

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