David Eppstein - Publications

J. Graph Algorithms and Applications

• Subgraph isomorphism in planar graphs and related problems.
  D. Eppstein.
  Tech. Rep. 94-25, ICS, UCI, 1994.
  6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 632–640.
  arXiv:cs.DS/9911003.
  J. Graph Algorithms and Applications 3 (3): 1–27, 1999.

  Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper, "Diameter and treewidth in minor-closed graph families", presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.

• Geometric thickness of complete graphs.
  M. Dillencourt, D. Eppstein, and D. S. Hirschberg.
  6th Int. Symp. Graph Drawing, Montreal, August 1998.
  Springer, Lecture Notes in Comp. Sci. 1547, 1998, pp. 102–110.
  arXiv:math.CO/9910185.
  J. Graph Algorithms and Applications 4 (3): 5–17, 2000 (special issue for GD98).

  We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.

• Fast approximation of centrality.
  D. Eppstein and J. Wang.
  arXiv:cs.DS/0009005.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 228–229.
  J. Graph Algorithms & Applications 8 (1): 39–45, 2004.

  We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.

  (SODA paper)

• Small maximal independent sets and faster exact graph coloring.
  D. Eppstein.
  arXiv:cs.DS/0011009.
  7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 462–470.
  J. Graph Algorithms and Applications (special issue for WADS'01) 7 (2): 131–140, 2003.

  We show that any graph can be colored in time O(2.415ⁿ), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.

  (WADS talk slides)

• Confluent drawings: visualizing non-planar diagrams in a planar way.
  M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
  arXiv:cs.CG/0212046.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
  J. Graph Algorithms and Applications (special issue for GD'03) 9 (1): 31–52, 2005.

  We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.

• The traveling salesman problem for cubic graphs.
  D. Eppstein.
  arXiv:cs.DS/0302030.
  8th Worksh. Algorithms and Data Structures, Ottawa, 2003.
  Springer, Lecture Notes in Comp. Sci. 2748, 2003, pp. 307–318.
  J. Graph Algorithms and Applications 11 (1): 61–81, 2007.

  We find improved exponential-time algorithms for exact solution of the traveling salesman problem on graphs of maximum degree three and four. We also consider related problems including counting the number of Hamiltonian cycles in such graphs.

  (WADS talk slides)

• Upright-quad drawing of \(st\)-planar learning spaces.
  D. Eppstein.
  arXiv:cs.CG/0607094.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 282–293.
  J. Graph Algorithms and Applications 12 (1): 51–72, 2008 (special issue for GD'06).

  We consider graph drawing algorithms for learning spaces, a type of \(st\)-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any \(st\)-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an \(st\)-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.

  (GD'06 talk slides)

• Recognizing partial cubes in quadratic time.
  D. Eppstein.
  arXiv:0705.1025.
  19th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 2008, pp. 1258–1266.
  J. Graph Algorithms and Applications 15 (2): 269–293, 2011.

  We show how to test whether a graph is a partial cube, and if so embed it isometrically into a hypercube, in time O(n²), improving previous O(nm)-time solutions; here n is the number of vertices and m is the number of edges. The ideas are to use bit-parallelism to speed up previous approaches to the embedding step, and to verify that the resulting embedding is isometric using an all-pairs shortest path algorithm from "algorithms for media".

  (slides)

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

• Finding large clique minors is hard.
  D. Eppstein.
  arXiv:0807.0007.
  J. Graph Algorithms and Applications 13 (2): 197–204, 2009.

  Proves that it's NP-complete to compute the Hadwiger number of a graph.

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

• Optimal angular resolution for face-symmetric drawings.
  D. Eppstein and K. Wortman.
  arXiv:0907.5474.
  J. Graph Algorithms and Applications 15 (4): 551–564, 2011.

  We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.

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

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

• Guest editor's foreword.
  D. Eppstein and E. Gansner.
  Journal of Graph Algorithms and Applications 15 (2): 3–5, 2011.
  (Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009)
  
• 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.

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

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

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

• Planar induced subgraphs of sparse graphs.
  G. Borradaile, D. Eppstein, and P. Zhu.
  arXiv:1408.5939.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 1–12.
  J. Graph Algorithms & Applications 19 (1): 281–297, 2015.

  We investigate the number of vertices that must be deleted from an arbitrary graph, in the worst case as a function of the number of edges, in order to planarize the remaining graph. We show that m/5.22 vertices are sufficient and m/(6 − o(1)) are necessary, and we also give bounds for the number of deletions needed to achieve certain subclasses of planar graphs.

• The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings.
  M. J. Bannister, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
  arXiv:1408.1422.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 149–161.
  J. Graph Algorithms & Applications 19 (2): 619–656, 2015 (special issue for GD'14).

  We show that many standard graph drawing methods have algebraic solutions described by polynomials that can have unsolvable Galois groups, and that can have Galois groups whose order is divisible by large prime numbers. As a consequence certain models of exact algebraic computation are unable to construct these drawings.

• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth.
  M. J. Bannister and D. Eppstein.
  arXiv:1408.6321.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 210–221.
  J. Graph Algorithms & Applications 22 (4): 577–606, 2018.

  We show how to express in monadic second-order logic the problems of drawing a graph with a fixed number of crossings on a one or two page book layout. By applying Courcelle's theorem, we obtain fixed-parameter tractable algorithms for these problems, parameterized by treewidth.

• Simple recognition of Halin graphs and their generalizations.
  D. Eppstein.
  arXiv:1502.05334.
  J. Graph Algorithms & Applications 20 (2): 323–346, 2016.

  We describe and implement a simple linear time algorithm for recognizing Halin graphs based on two simplifications of triples of degree-three vertices in such graphs. Removing some auxiliary data from the algorithm causes it to recognize a broader class of graphs that we call the D3-reducible graphs. We study the properties of these graphs, showing that they share many properties with the Halin graphs.

• Rooted cycle bases.
  D. Eppstein, J. M. McCarthy, and B. E. Parrish.
  arXiv:1504.04931.
  14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
  Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 339–350.
  J. Graph Algorithms & Applications 21 (4): 663–686, 2017.

  We consider the problem of finding a cycle basis for a graph in which all basis cycles contain a specified edge. We characterize the graphs having such a basis in terms of their vertex connectivity, we show that the minimum weight cycle basis with this constraint can be found in polynomial time and is weakly fundamental, and we show that finding a fundamental cycle basis with this constraint is NP-hard but fixed-parameter tractable.

  (Slides)

• Metric dimension parameterized by max leaf number.
  D. Eppstein.
  arXiv:1506.01749.
  J. Graph Algorithms & Applications 19 (1): 313–323, 2015.

  We prove that when a graph of bounded size has its edges subdivided to form a larger graph, it is still possible to find its metric dimension by a fixed-parameter tractable algorithm, parameterized by the pre-subdivision size of the graph.

• Triangle-free penny graphs: degeneracy, choosability, and edge count.
  D. Eppstein.
  arXiv:1708.05152.
  Proc. 25th Int. Symp. Graph Drawing, Boston, Massachusetts, 2017.
  Springer, Lecture Notes in Comp. Sci. 10692 (2018), pp. 506–513.
  J. Graph Algorithms & Applications 22 (3): 483–499 (special issue for GD 2017), 2018.

  A penny graph is the contact graph of unit disks: each disk represents a vertex of the graph, no two disks can overlap, and each tangency between two disks represents an edge in the graph. We prove that, when this graph is triangle free, its degeneracy is at most two. As a consequence, triangle-free penny graphs have list chromatic number at most three. We also show that the number of edges in any such graph is at most 2n − Ω(√n). The journal version uses the alternative title "Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs".

  (Slides)

• The effect of planarization on width.
  D. Eppstein.
  arXiv:1708.05155.
  Proc. 25th Int. Symp. Graph Drawing, Boston, Massachusetts, 2017.
  Springer, Lecture Notes in Comp. Sci. 10692 (2018), pp. 560–572.
  J. Graph Algorithms & Applications 22 (3): 461–481 (special issue for GD 2017), 2018.

  We study what happens to nonplanar graphs of low width (for various width measures) when they are made planar by replacing crossings by vertices. For treewidth, pathwidth, branchwidth, clique-width, and tree-depth, this replacement can blow up the width from constant to linear. However, for bandwidth, cutwidth, and carving width, graphs of bounded width stay bounded when we planarize them.

  (Slides)

• Bipartite and series-parallel graphs without planar Lombardi drawings.
  D. Eppstein.
  arXiv:1906.04401.
  Proc. 31st Canadian Conference on Computational Geometry, Edmonton, Canada, 2019, pp. 17–22.
  J. Graph Algorithms & Applications 25 (1): 549–562, 2021.

  Not every bipartite planar graph has a planar Lombardi drawing. Not every plane series parallel graph has a planar Lombardi drawing with the same embedding. The proof involves the properties of cycles of circular-arc-quadrilaterals all sharing the same two vertices, with equal and sharp vertex angles.

  (Slides)

• On the biplanarity of blowups.
  D. Eppstein.
  arXiv:2301.09246.
  Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023 (best paper award).
  Springer, Lecture Notes in Computer Science 14465 (part I), pp. 3–17.
  J. Graph Algorithms & Applications 28 (2): 83–99, 2024.
  

  Expanding every vertex of a planar graph to two independent copies can produce a graph of thickness greater than two, disproving a conjecture of Ellen Gethner. We also investigate special cases of this construction for which the thickness is two.

  (talk slides)

• Quasipolynomiality of the smallest missing induced subgraph.
  D. Eppstein, A. Lincoln, and V. V. Williams.
  arXiv:2306.11185.
  J. Graph Algorithms & Applications 27 (5): 329–339, 2023.

  The smallest graph that is not an induced subgraph of a given graph can be found in time \(n^{O(\log n)}\). The exponent is optimal, up to constant factors, under the exponential time hypothesis.