David Eppstein - Publications

2012

• The h-index of a graph and its application to dynamic subgraph statistics.
  D. Eppstein and E. S. Spiro.
  arXiv:0904.3741.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada.
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 278–289.
  J. Graph Algorithms and Applications 16 (2): 543–567, 2012.

  We define the h-index of a graph to be the maximum h such that the graph has h vertices each of which has degree at least h. We show that the h-index, and a partition of the graph into high and low degree vertices, may be maintained in constant time per update. Based on this technique, we show how to maintain the number of triangles in a dynamic graph in time O(h) per update; this problem is motivated by Markov Chain Monte Caro simulation of the Exponential Random Graph Model used for simulation of social networks. We also prove bounds on the h-index for scale-free graphs and investigate the behavior of the h-index on a corpus of real social networks.

  (Slides)

• Drawing graphs in the plane with a prescribed outer face and polynomial area.
  E. Chambers, D. Eppstein, M. T. Goodrich, and M. Löffler.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 129–140.
  arXiv:1009.0088.
  J. Graph Algorithms and Applications 16 (2): 243–259, 2012.

  Tutte's method of spring embeddings allows any triangulated planar graph to be drawn so that the outer face has any pre-specified convex shape, but it may place vertices exponentially close to each other. Alternative graph drawing methods provide polynomial-area straight line drawings but do not allow the outer face shape to be specified. We describe a drawing method that combines both properties: it has polynomial area, and can match any pre-specified shape of the outer face, even a shape in which some of the vertices have 180 degree angles. We apply our results to drawing polygonal schemas for graphs embedded on surfaces of positive genus.

• Lombardi drawings of graphs.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 195–207.
  arXiv:1009.0579.
  Invited talk at 7th Dutch Computational Geometry Day, Eindhoven, the Netherlands, 2010.
  J. Graph Algorithms and Applications 16 (1): 85–108, 2012 (special issue for GD 2010).

  In honor of artist Mark Lombardi, we define a Lombardi drawing to be a drawing of a graph in which the edges are drawn as circular arcs and at each vertex they are equally spaced around the vertex so as to achieve the best possible angular resolution. We describe algorithms for constructing Lombardi drawings of regular graphs, 2-degenerate graphs, graphs with rotational symmetry, and several types of planar graphs. A program for the rotationally symmetric case, the Lombardi Spirograph, is available online.

• Extended dynamic subgraph statistics using h-index parameterized data structures.
  D. Eppstein, M. T. Goodrich, D. Strash, and L. Trott.
  Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Hawaii, 2010.
  Springer, Lecture Notes in Comp. Sci. 6508, 2010, pp. 128–141.
  arXiv:1009.0783.
  Theor. Comput. Sci. 447: 44–52, 2012 (special issue for COCOA 2010).

  An earlier paper with Spiro at WADS 2009 provided dynamic graph algorithms for counting how many copies of each possible type of subgraph there are in a larger undirected graph, when the subgraphs have at most three vertices. This paper extends the method to directed graphs and to larger numbers of vertices per subgraph.

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

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

• Planar and poly-arc Lombardi drawings.
  C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Löffler, and M. Nöllenburg.
  Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
  Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 308–319.
  arXiv:1109.0345.
  J. Computational Geometry 9 (1): 328–355, 2018.

  We extend Lombardi drawing (in which each edge is a circular arc and the edges incident to a vertex must be equally spaced around it) to drawings in which edges are composed of multiple arcs, and we investigate the graphs that can be drawn in this more relaxed framework.

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

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

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

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

• Solving single-digit Sudoku subproblems.
  D. Eppstein.
  arXiv:1202.5074.
  6th International Conference on Fun with Algorithms (FUN 2012), Venice, Italy, 2012.
  Springer, Lecture Notes in Comp. Sci. 7288, 2012, pp. 142–153.

  We find an algorithm for making all possible deductions based on the set of candidate locations for a single digit in a Sudoku puzzle; the problem is NP-hard, and our algorithm takes exponential time, but the mild form of the exponential allows it to be fast for practical problem sizes.

  (Slides)

• Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets.
  G. Borradaile and D. Eppstein.
  arXiv:1206.2254.
  24th Canadian Conference on Computational Geometry (CCCG 2012), Prince Edward Island, Canada, 2012, pp. 311–316.
  Comp. Geom. Theory & Applications 49: 8–16, 2015 (special issue for CCCG 2012).

  When a planar point set has the property that its Delaunay triangulation has no large angles, we show how to connect it by a plane graph (having linearly many additional Steiner vertices) in which the distances between the original points are approximations to their Euclidean distance, and in which the total graph weight is at most a constant times the minimum spanning tree weight. The time to construct this graph is near-linear, the same as for integer sorting. We use this result to approximate the traveling salesman problem, for these point sets, in the same time bound.

• UOBPRM: a uniform distributed obstacle-based PRM.
  H.-Y. Yeh, S. Thomas, D. Eppstein, and N. Amato.
  IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012), Vilamoura, Algarve, Portugal, 2012, pp. 2655–2662.

  We use a method based on intersecting obstacles with line segments in order to uniformly sample from obstacle surfaces in the probabilistic roadmap method for robot motion planning.

• Diamond-kite meshes: adaptive quadrilateral meshing and orthogonal circle packing.
  D. Eppstein.
  arXiv:1207.5082.
  21st International Meshing Round Table, San Jose, California, 2012, pp. 261–277.
  Engineering with Computers 30 (2): 223–235 (special issue for the 21st Int. Meshing Roundtable), 2014.

  We describe a recursive subdivision of the plane into quadrilaterals in the form of rhombi and kites with 60, 90, and 120 degree angles. The vertices of the resulting quadrilateral mesh form the centers of a set of circles that cross orthogonally for every two adjacent vertices, and it has many other properties that are important in finite element meshing.

  (Slides)

• A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing.
  D. Eppstein.
  Invited talk at EuroGIGA Midterm Conference, Prague, Czech Republic, 2012.
  Discrete Comput. Geom. 52 (3): 515–550, 2014 (Special issue for SoCG 2013).

  This talk and journal paper combines the results from "Planar Lombardi drawings for subcubic graphs" and "The graphs of planar soap bubbles". It uses three-dimensional hyperbolic geometry to define a partition of the plane into cells with circular-arc boundaries, given an input consisting of (possibly overlapping) circular disks and disk complements, which remains invariant under Möbius transformations of the input. We use this construction as a tool to construct planar Lombardi drawings of all 3-regular planar graphs; these are graph drawings in which the edges are represented by circular arcs meeting at equal angles at each vertex. We also use it to characterize the graphs of two-dimensional soap bubble clusters as being exactly the 2-vertex-connected 3-regular planar graphs.

• Planar Lombardi drawings for subcubic graphs.
  D. Eppstein.
  arXiv:1206.6142.
  20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
  Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 126–137.
  

  We show that every planar graph of maximum degree three has a planar Lombardi drawing and that some but not all 4-regular planar graphs have planar Lombardi drawings. The proof idea combines circle packings with a form of Möbius-invariant power diagram for circles, defined using three-dimensional hyperbolic geometry.

  For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".

  (Slides)

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

• On the density of maximal 1-planar graphs.
  F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer, and J. Reislhuber.
  20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
  Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 327–338.
  

  A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge, and maximal 1-planar if it is 1-planar but adding any edge would force more than one crossing on some edge or edges. Although maximal 1-planar graphs on n vertices may have as many as 4n − 8 edges, we show that there exist maximal 1-planar graphs with as few as 45n/17 + O(1) edges.

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

• The graphs of planar soap bubbles.
  D. Eppstein.
  arXiv:1207.3761.
  Proc. 29th ACM Symp. on Computational Geometry, Rio de Janeiro, 2013, pp. 27–36.

  We characterize the graphs of two-dimensional soap bubble clusters as being exactly the bridgeless 3-regular planar graphs. The proof uses the Möbius invariance of the properties characterizing these clusters together with our previous circle packing method for constructing Lombardi drawings of graphs.

  For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".

  (Slides)