David Eppstein - Publications

2013

• The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing.
  D. Eppstein.
  arXiv:0709.4087.
  Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
  Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 78–89.
  J. Graph Algorithms and Applications 17 (1): 35–55, 2013.

  Defines a class of orthogonal graph drawings formed by a point set in three dimensions for which axis-parallel line contains zero or two vertices, with edges connecting pairs of points on each nonempty axis-parallel line. Shows that the existence of such a drawing can be defined topologically, in terms of certain two-dimensional surface embeddings of the same graph. Based on this equivalence, describes algorithms, graph-theoretic properties, and hardness results for graphs of this type.

  (Slides from talk at U. Arizona, February 2008 – Slides from GD08) )

• Flows in one-crossing-minor-free graphs.
  E. Chambers and D. Eppstein.
  arXiv:1007.1484.
  Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 241–252.
  J. Graph Algorithms and Applications 17 (3): 201–220, 2013.

  We show that the maximum flow problem can be solved in near-linear time for K₅-minor-free and K_3,3-minor-free graphs. The same result also holds for H-minor-free graphs when H can be embedded in the plane with one crossing and a structural decomposition of the input flow graph is given.

• Drawing trees with perfect angular resolution and polynomial area.
  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. 183–194.
  arXiv:1009.0581.
  Discrete Comput. Geom. 49 (2): 157–182, 2013.

  We consider balloon drawings of trees, in which each subtree of the root is drawn recursively within a disk, and these disks are arranged radially around the root, with the edges at each node spaced equally around the node so as to achieve the best possible angular resolution. If we are allowed to permute the children of each node, then we show that a drawing of this type can be made in which all edges are straight line segments and the area of the drawing is a polynomial multiple of the shortest edge length. However, if the child ordering is prescribed, exponential area might be necessary. We show that, if we relax the requirement of straight line edges and draw the edges as circular arcs (a style we call Lombardi drawing) then even with a prescribed child ordering we can achieve polynomial area.

• Optimal 3D angular resolution for low-degree graphs.
  D. Eppstein, M. Löffler, E. Mumford, and M. Nöllenburg.
  Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
  Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 208–219.
  arXiv:1009.0045.
  J. Graph Algorithms and Applications 17 (3): 173–200, 2013.

  We show how to draw any graph of maximum degree three in three dimensions with 120 degree angles at each vertex or bend, and any graph of maximum degree four in three dimensions with the angles of the diamond lattice at each vertex or bend. In each case there are no crossings and the number of bends per edge is a small constant.

• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension.
  D. Eppstein and M. Löffler.
  Proc. 27th ACM Symp. on Computational Geometry, Paris, 2011, pp. 361–368.
  arXiv:1103.2575.
  Discrete Comput. Geom. 50 (1): 1–21, 2013.

  Suppose that P is the intersection of n halfspaces in D dimensions, but that the bounded faces of P are at most d-dimensional, for some d that is much smaller than D. Then in this case we show that the number of vertices of P is O(n^d), independent of D. We also investigate related bounds on the number of bounded faces of all dimensions of P, and algorithms for efficiently listing the vertices and bounded faces of P.

• On 2-site Voronoi diagrams under geometric distance functions.
  G. Barequet, M. Dickerson, D. Eppstein, D. Hodorkovsky, and K. Vyatkina.
  27th Eur. Worksh. Comp. Geom., Antoniushaus Morschach, Switzerland, 2011, pp. 59–62.
  Proc. 8th Int. Symp. Voronoi Diagrams in Science and Engineering, Qing Dao, China, 2011, pp. 31–38.
  arXiv:1105.4130.
  J. Computer Science and Technology 28 (2): 267–277, 2013.

  We study the combinatorial complexity of generalized Voronoi diagrams that determine the closest two point sites to a query point, where the distance from the query point to a pair of sites is a combination of the individual distances to the sites and the distance from one site in the pair to the other.

• Category-based routing in social networks: membership dimension and the small-world phenomenon.
  D. Eppstein, M. T. Goodrich, M. Löffler, D. Strash, and L. Trott.
  Workshop on Graph Algorithms and Applications, Zürich, Switzerland, July 2011.
  International Conference on Computational Aspects of Social Networks (CASoN 2011), Salamanca, Spain, October 2011.
  arXiv:1108.4675.
  Theor. Comput. Sci. 514: 96–104, 2013. (Special issue on Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello)
  

  We investigate greedy routing schemes for social networks, in which participants know categorical information about some other participants and use it to guide message delivery by forwarding messages to neighbors that have more categories in common with the eventual destination. We define the membership dimension of such a scheme to be the maximum number of categories that any individual belongs to, a natural measure of the cognitive load of greedy routing on its participants. And we show that membership dimension is closely related to the small world phenomenon: a social network can be given a category system with polylogarithmic membership dimension that supports greedy routing if, and only if, the network has polylogarithmic diameter.

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

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

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

• Antimatroids and balanced pairs.
  D. Eppstein.
  arXiv:1302.5967.
  Order 31 (1): 81–99, 2014. Erratum (with V. Wiechert).

  We generalize the 1/3-2/3 conjecture, according to which every partial order should have a pair of items that are nearly equally likely to appear in either order in a random linear extension, to antimatroids, and we prove it for several specific types of antimatroid.

• Grid minors in damaged grids.
  D. Eppstein.
  arXiv:1303.1136.
  Electronic J. Combinatorics 21(3), Paper P3.20, 2014.

  We give tight bounds on the size of the largest remaining grid minor in a grid graph from which a given number of vertices have been deleted, and study several related problems.

• Combinatorial pair testing: distinguishing workers from slackers.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  arXiv:1305.0110.
  13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario.
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 316–327.
  

  We study the problem of distinguishing workers (people who complete their assigned tasks) from slackers (people who do not contribute towards the completion of their tasks) by grouping people in pairs and assigning a task to each group.

• 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
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 97–108.
  J. Graph Algorithms and Applications 22 (1): 23–49, 2018. (Special issue on Graph Drawing Beyond Planarity.)
  

  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.

  (Slides)

• Knowledge Spaces: Applications in Education.
  J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
  Springer, 2013.

  This edited volume collects experiences with automated learning systems based on the theory of knowledge spaces, and mathematical explorations of the theory of knowledge spaces and their efficient implementation.

• Learning sequences: an efficient data structure for learning spaces.
  D. Eppstein.
  In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
  Springer, 2013, pp. 287–304.

  We show how to represent a learning space by a small family of learning sequences, orderings of the items in a learning sequence that are consistent with their prerequisite relations. This representation allows for the rapid generation of the family of all consistent knowledge states and the efficient assessment of the state of knowledge of a human learner.

• Projection, decomposition, and adaption of learning spaces.
  D. Eppstein.
  In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
  Springer, 2013, pp. 305–322.

  In another chapter of the same book we used learning sequences to represent learning spaces and perform efficient knowledge assessment of a human learning. In this chapter we show how to use the same data structure to build learning spaces on a sample of the items of a larger learning space (an important subroutine in knowledge assessment) and to modify a learning space to more accurately model students.

• A brief history of curves in graph drawing.
  D. Eppstein.
  Invited survey talk at Workshop on Drawing Graphs and Maps with Curves, Dagstuhl, Germany, April 2013.
  Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151), S. G. Kobourov, M. Nöllenburg, and M. Teillaud, eds., Dagstuhl Reports 3(4): 40–46, 2013.

  (Slides)

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

• Universal point sets for planar graph drawings with circular arcs.
  P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, and A. Wolff.
  HAL-Inria open archive oai:hal.inria.fr:hal-00846953.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.
  J. Graph Algorithms and Applications 18 (3): 313–324, 2014.

  For every positive integer n, there exists a set of n points on a parabola, with the property that every n-vertex planar graph can be drawn without crossings with its vertices at these points and with its edges drawn as circular arcs.

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

• Superpatterns and universal point sets.
  M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein.
  arXiv:1308.0403.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 208–219.
  Bannister's talk on this paper won the GD2013 best presentation award.
  J. Graph Algorithms & Applications 18 (2): 177–209, 2014 (special issue for GD'13).

  A superpattern of a set of permutations is a permutation that contains as a pattern every permutation in the set. Previously superpatterns had been considered for all permutations of a given length; we generalize this to sets of permutations defined by forbidden patterns; we show that the 213-avoiding permutations have superpatterns half the length of the known bound for all permutations, and that any proper permutation subclass of the 213-avoiding permutations has near-linear superpatterns. We apply these results to the construction of universal point sets, sets of points that can be used as the vertices of drawings of all n-vertex planar graphs. We use our 213-avoiding superpatterns to construct universal sets of size approximately \(n^2/4\), and we also construct near-linear universal sets for graphs of bounded pathwidth.

• Drawing arrangement graphs in small grids, or how to play planarity.
  D. Eppstein.
  arXiv:1308.0066.
  21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 436–447.
  J. Graph Algorithms & Applications 18 (2): 211–231, 2014 (special issue for GD'13).

  The planarity game involves rearranging a scrambled line arrangement graph to make it planar. We show that the resulting graphs have drawings in grids of area n^7/6, much smaller than the quadratic size bound for grid drawings of planar graphs, and we provide a strategy for planarizing these graphs that is simple enough for human puzzle solving.

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

• Small superpatterns for dominance drawing.
  M. J. Bannister, W. E. Devanny, and D. Eppstein.
  arXiv:1310.3770.
  Analytic Algorithmics and Combinatorics (ANALCO14), Portland, Oregon, 2014, pp. 92–103.

  We construct small universal point sets for dominance drawings of classes of acyclic graphs, by finding forbidden patterns in the permutations determined by these drawings and proving the existence of small superpatterns for the permutations with these patterns forbidden. In particular, dominance drawings of the Hasse diagrams of width-2 partial orders have universal point sets of size O(n^3/2), derived from superpatterns of the same size for the 321-avoiding permutations, and dominance drawings of st-planar graphs have universal point sets of size O(n log n), derived from superpatterns for riffle shuffles.

• Listing all maximal cliques in large sparse real-world graphs.
  D. Eppstein, M. Löffler, and D. Strash.
  J. Experimental Algorithmics 18 (3): 3.1, 2013 (special issue for SEA).

  This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011. We show how to list all maximal cliques in graphs of bounded degeneracy in time that is linear in the size of the graph and near-optimal in the degeneracy, and we show that low degeneracy explains the good behavior of the algorithm in our experiments on large real-world social networks.