Miscellanous graph theory
Parallel algorithmic techniques for combinatorial computation.
D. Eppstein and Z. Galil.
Ann. Rev. Comput. Sci. 3: 233–283, 1988.
Invited talk by Z. Galil, 16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
Springer, Lecture Notes in Comp. Sci. 372, 1989, pp. 304–318.This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.
Efficient sequential and parallel algorithms for computing recovery points in trees and paths.
M. Chrobak, D. Eppstein, G.F. Italiano, and M. Yung.
2nd ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1991, pp. 158–167.
ALCOM Report 91-74, University of Rome, 1991.Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.
Clustering for faster network simplex pivots.
D. Eppstein.
Tech. Rep. 93-19, ICS, UCI, 1993.
5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 160–166.
Networks 35 (3): 173–180, 2000.Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.
Minimum range balanced cuts via dynamic subset sums.
D. Eppstein.
Tech. Rep. 95-10, ICS, UCI, 1995.
J. Algorithms 23: 375–385, 1997.Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.
The weighted maximum-mean subtree and other bicriterion subtree problems.
J. Carlson and D. Eppstein.
arXiv:cs.CG/0503023.
Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
Springer, Lecture Notes in Comp. Sci. 4059, 2006, pp. 397–408.We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".
Interconnect criticality driven delay relaxation.
L. Singhal, E. Bozorgzadeh, and D. Eppstein.
IEEE Trans. CAD 26 (10): 1803–1817, 2007.We consider a problem of assigning delays to components in a circuit so that each component is part of a critical path, but the number of edges belonging to critical paths is minimized. We show the problem to be NP-complete via a reduction from finding independent dominating sets in bipartite graphs minimizing dominated edges, and give experimental results on heuristics.
Graph-theoretic solutions to computational geometry problems.
D. Eppstein.
Invited talk, the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France, 2009.
Springer, Lecture Notes in Comp. Sci. 5911, 2009, pp. 1–16.
arXiv:0908.3916.We survey problems in computational geometry that may be solved by constructing an auxiliary graph from the problem and solving a graph-theoretic problem on the auxiliary graph. The problems considered include the art gallery problem, partitioning into rectangles, minimum diameter clustering, bend minimization in cartogram construction, mesh stripification, optimal angular resolution, and metric embedding.
Going off-road: transversal complexity in road networks.
D. Eppstein, M. T. Goodrich, and L. Trott.
arXiv:0909.2891.
Proc. 17th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems, Seattle, 2009, pp. 23–32.Shows both theoretically and experimentally that the number of times a random line crosses a road network is asymptotically upper bounded by the square root of the number of road segments.
Paired approximation problems and incompatible inapproximabilities.
D. Eppstein.
arXiv:0909.1870.
21st ACM-SIAM Symp. Discrete Algorithms, Austin, Texas, 2010, pp. 1076–1086.Considers situations in which two hard approximation problems are presented by means of a single input. In many cases it is possible to guarantee that one or the other problem can be approximated to within a better approximation ratio than is possible for approximating it as a single problem. For instance, it is possible to find either a (1+ε)-approximation to a 1-2 TSP defined from a graph or a nε-approximation to the maximum independent set of the same graph, despite lower bounds showing nonexistence of approximation schemes for 1-2 TSP and nonexistence of approximations better than n1 − ε for independent set. However, for some other pairs of problems, such as hitting set and set cover, we show that solving the paired problem approximately is no easier than solving either problem independently.
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.
Automated generation of linkage loop equations for planar 1-dof linkages, demonstrated up to 8-bar.
B. E. Parrish, J. M. McCarthy, and D. Eppstein.
Proc. ASME 2014 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Vol. 5A: 38th Mechanisms and Robotics Conference, Buffalo, New York, USA, August 17-20, 2014, paper no. DETC2014-35263.
J. Mechanisms and Robotics 7 (1): 011006, 2015.This paper reports on an implementation of an algorithm for constructing the configuration space of two-dimensional linkages with one degree of freedom.
(eScholarship conference version – eScholarship journal version)
ERGMs are hard.
M. J. Bannister, W. E. Devanny, and D. Eppstein.
arXiv:1412.1787.ERGMs (exponential random graph models) are used in social science to describe probability distributions on graphs that are supposed to mimic real-world social networks. However, we show that (with features that are standard in the social science application) the distributions given by these models can be computationally infeasible to sample from or to approximate the probability of seeing a given graph.
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.
The computational hardness of dK-series.
W. E. Devanny, D. Eppstein, and B. Tillman.
NetSci2016 poster session, Seoul, Korea.The dK-series is an extension of the degree sequence of a graph to a d-dimensional tensor, describing the number of d-tuples of vertices with each possible combination of degrees and adjacencies. As we show, it is NP-hard to determine whether such a tensor represents a valid graph, for any d ≥ 3, or for d = 2 if the number of triangles in the graph is also specified (or constrained to be zero).
Models and algorithms for graph watermarking.
D. Eppstein, M. T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, and M. Torres.
arXiv:1605.09425.
Proc. 19th Information Security Conference (ISC 2016), Honolulu, Hawaii.
Springer, Lecture Notes in Comp. Sci. 9866 (2016), pp. 283–301.We show how to modify a small number of edges in a large social network in order to make the modified copy easy to identify, even if an adversary tries to hide the modification by permuting the vertices and flipping a much larger number of edges. The result depends on the random fluctuation of vertex degrees in such networks, and the ability to uniquely identify vertices by their adjacencies to a small number of high-degree landmark vertices. This paper won the best student paper award at ISC for its student co-authors Lam, Mamano, and Torres.
Low-stretch spanning trees of graphs with bounded width.
G. Borradaile, E. Chambers, D. Eppstein, W. Maxwell, and A. Nayyeri.
arXiv:2004.08375.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19.We describe a random distribution on the spanning trees of bounded-bandwidth graphs such that each edge has bounded expected stretch, along with several related results for other kinds of graph widths.
On the treewidth of Hanoi graphs.
D. Eppstein, D. Frishberg, and W. Maxwell.
arXiv:2005.00179.
Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
Leibniz International Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21.
Theor. Comput. Sci. 906: 1–17, 2022.The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of np − 1.
Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs.
D. Eppstein and D. Frishberg.
arXiv:2111.03898.
Proc 34th International Symposium on Algorithms and Computation (ISAAC 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 283, 2022, pp. 30:1–30:13.A random walk on the independent sets or dominating sets of a graph mixes rapidly for graphs of bounded treewidth, and a random walk on maximal independent sets mixes rapidly for graphs of bounded carving width.
Improved mixing for the convex polygon triangulation flip walk.
D. Eppstein and D. Frishberg.
arXiv:2207.09972.
Proc. 50th EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 261, 2023, pp. 56:1–56:17.The associahedron is a polytope whose vertices represent the triangulations of a convex polygon, and whose edges represent flips connecting one triangulation to another. We show that a random walk on the edges of this polytope rapidly converges to the uniform distribution on triangulations. However, we also show that the associahedron does not have constant expansion.
On the complexity of embedding in graph products.
T. Biedl, D. Eppstein, and T. Ueckerdt.
arXiv:2303.17028.
Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 77–88.
Computing in Geometry and Topology 4 (2): 5:1–5:18, 2025.Row treewidth (embedding a graph as a subgraph of a strong product of a path with a low treewidth graph), row pathwidth, and row tree-depth are all NP-hard.
Lower bounds for non-adaptive shortest path relaxation.
D. Eppstein.
arXiv:2305.09230.
Proc. 18th Algorithms and Data Structures Symposium (WADS 2023).
Springer, Lecture Notes in Computer Science 13079 (2023), pp. 416–429.The Bellman–Ford algorithm for single-source shortest paths operates by relaxation steps, in which it checks for a given edge whether the best path it knows to the start of the edge, plus the edge itself, is better than the path it already knows to the end of the edge. We prove that, up to constant factors, Bellman–Ford is optimal among algorithms that use relaxation in an edge ordering that does not depend on the results of earlier relaxation steps.
Widths of geometric graphs.
D. Eppstein.
Invited talk, Workshop on Parameterized Algorithms for Geometric Problems, CG Week 2023.Many computational geometry problems can be solved by transforming them into a graph problem on a geometric graph. When the graph has low width, for some form of graph width, this can often lead to efficient classical or parameterized algorithms. We survey the geometric graphs that always have low width, the geometric graphs that can have high width, and the opportunities for parameterization obtained by studying low-width instances of graphs that sometimes have high width.
Geometric graphs with unbounded flip-width.
D. Eppstein and R. McCarty.
arXiv:2306.12611.
Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 197–208.We show that many constructions for dense geometric graphs produce graphs of unbounded flip-width, frustrating the search for natural classes of graphs that have bounded flip-width but unbounded twin-width.
Games on game graphs.
D. Eppstein. AMS Special Session on Serious Recreational Mathematics, Joint Mathematics Meetings, San Francisco, 2024.This talk surveys graph parameters defined from pursuit-evasion games on graphs, including cop-number, treewidth, and flip-width, and the values of these parameters on graphs derived from games and puzzles.
What is ... treewidth?.
D. Eppstein.
Notices of the American Mathematical Society 72 (2): 172–175, 2025.We survey graph treewidth at a high level. The focus is on applications of treewidth to various areas of mathematics.
Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing.
D. Eppstein, M. T. Goodrich, and S. Liu.
arXiv:2505.10789.
Proc. 33rd Annual European Symposium on Algorithms (ESA 2025).
Leibniz International Proceedings in Informatics (LIPIcs) 351, 2025, pp. 69:1–69:17.In graphs of bounded bandwidth, the number of vertices per level of a breadth-first search tree is at most polylogarithmic, with the exponent of the polylogarithm both upper and lower bounded by functions of the bandwidth. This has applications to the Cuthull-McKee heuristic and reverse Cuthull-McKee heuristic in sparse numerical algebra, to reconstructing an unknown graph by shortest distance queries, and to drawing graphs as arc diagrams of small height.
Decremental greedy polygons and polyhedra without sharp angles.
D. Eppstein.
arXiv:2507.04538.
Proc. 37th Canadian Conference on Computational Geometry, 2025, pp. 85–91.For given elements and a quality function of an element in a subset, monotonically non-increasing with respect to removals of other elements, we can find the max-min-quality subset by a decremental greedy algorithm that repeatedly removes low-quality subsets. We apply this method to find the max-min-angle polygon for points in the plane, the max-min-weight cycle in a directed graph, and several generalizations of both problems.
Hamiltonian cycles in subdivided doubles.
D. Eppstein.
arXiv:2510.18359.
Ars Mathematica Contemporanea, to appear.The subdivided double construction turns a 4-regular graph into a bigger 4-regular graph, by subdividing each edge and doubling each vertex. We prove that the resulting graphs, which include the Folkman graph, have the following curious property: every Hamiltonian cycle (of which there are exponentially many) is complementary to another Hamiltonian cycle.