Other journals and periodicals
Trees in TeX.
D. Eppstein.
TUGboat 6 (1): 31, 1985.This note in the TeX user's group newsletter described a set of macros for drawing trees, using TeX's boxes-and-glue mechanisms to line up the nodes at each level of the tree.
(TeX source code – Nelson Beebe's TeX tree drawing bibliography)
On the NP-completeness of cryptarithms.
D. Eppstein.
SIGACT News 18 (3): 38–40, 1987.A cryptarithm (also known as an alphametic) is a puzzle in which the digits of a mathematical formula (typically addition of two large numbers) are replaced by letters; the goal is to determine which letter stands for which digits. If arithmetic is done in a polynomially large radix, the problem becomes NP-complete.
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.
Ten algorithms for Egyptian fractions.
D. Eppstein.
Mathematica in Education and Research 4 (2): 5–15, 1995.Number theory. I survey and implement in Mathematica several methods for representing rational numbers as sums of distinct unit fractions. One of the methods involves searching for paths in a certain graph using a k shortest paths heuristic.
A deterministic linear time algorithm for geometric separators and its applications.
D. Eppstein, G.L. Miller, and S.-H. Teng.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 99–108.
Fundamenta Informaticae 22: 309–330, 1995 (special issue on computational geometry).Teng and others previously showed that certain geometric graphs had small separators that could be found by lifting the graph to a sphere one dimension up and choosing a random great circle. Here we show that epsilon-cuttings and the method of conditional expectations can be used to guide a deterministic prune-and-search method for the same problem. Applications include finding the intersection graph of a collection of spheres and computing or approximating the maximum number of spheres having a common intersection.
Computing the discrepancy with applications to supersampling patterns.
D. P. Dobkin, D. Eppstein, and D. P. Mitchell.
ACM Trans. on Graphics 15 (4): 354–376, 1996.Combines "Computing the discrepancy" with experimental results of Mitchell on the discrepancies of various point sets, emphasizing the application of low-discrepancy sets to anti-aliasing in raytraced graphics.
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.
Zonohedra and Zonotopes.
D. Eppstein.
Tech. Rep. 95-53, ICS, UCI, 1995.
Mathematica in Education and Research 5 (4): 15–21, 1996.I use Mathematica to construct zonotopes and display zonohedra. Many examples are shown, including one used for a lower bound in "The centroid of points with approximate weights". This paper is also available in HTML and Mathematica notebook formats.
The crust and the beta-skeleton: combinatorial curve reconstruction.
N. Amenta, M. Bern, and D. Eppstein.
Graphical Models & Image Processing 60/2 (2): 125–135, 1998.We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points. There have been many follow-up papers suggesting alternative methods, generalizing the problem to the reconstruction of curves with sharp corners or to curves and surfaces in higher dimensions, etc.
Fast hierarchical clustering and other applications of dynamic closest pairs.
D. Eppstein.
9th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1998, pp. 619–628.
arXiv:cs.DS/9912014.
J. Experimental Algorithmics 5 (1): 1–23, 2000.This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.
The distribution of cycle lengths in graphical models for iterative decoding.
X. Ge, D. Eppstein, and P. Smyth.
arXiv:cs.DM/9907002.
Tech. Rep. 99-10, ICS, UCI, 1999.
IEEE Int. Symp. Information Theory, Sorrento, Italy, 2000.
IEEE Trans. Information Theory 47 (6): 2549–2553, 2001.We compute the expected numbers of short cycles of each length in certain classes of random graphs used for turbocodes, estimate the probability that there are no such short cycles involving a given vertex, and experimentally verify our estimates. The scarcity of short cycles may help explain the empirically observed accuracy of belief-propagation based error-correction algorithms. Note, the TR, conference, and journal versions of this paper have slightly different titles.
Tangent spheres and triangle centers.
D. Eppstein.
arXiv:math.MG/9909152.
Amer. Math. Monthly 108 (1): 63–66, 2001.Any four mutually tangent spheres determine three coincident lines through opposite pairs of tangencies. As a consequence, we define two new triangle centers. These centers arose as part of a compass-and-straightedge construction of Soddy circles; also available are some Mathematica calculations of trilinear coordinates for the new triangle centers.
Flipping cubical meshes.
M. Bern D. Eppstein, and J. Erickson.
arXiv:cs.CG/0108020.
10th Int. Meshing Roundtable, Newport Beach, 2001, pp. 19–29.
Engineering with Computers 18 (3): 173–187, 2002.We examine flips in which a set of mesh cells connected in a similar pattern to a subset of faces of a cube or hypercube is replaced by cells in the pattern of the complementary subset. We show that certain flip types preserve geometric realizability of a mesh, and use this to study the question of whether every topologically meshable domain is geometrically meshable. We also study flip graph connectivity, and prove that the flip graph of quadrilateral meshes has exactly two connected components.
Note that the Meshing Roundtable version was by Bern and Eppstein. Erickson was added as a co-author during the revisions for the journal version.
The minimum expectation selection problem.
D. Eppstein and G. Lueker.
10th Int. Conf. Random Structures and Algorithms, Poznan, Poland, August 2001.
arXiv:cs.DS/0110011.
Random Structures and Algorithms 21: 278–292, 2002.We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. Such problems can be viewed as a simple form of two-stage stochastic programming. We show that if d, the number of values in the support of the distributions, is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.
Algorithms for media.
D. Eppstein and J.-C. Falmagne.
arXiv:cs.DS/0206033.
Int. Conf. Ordinal and Symbolic Data Analysis, Irvine, 2003.
Discrete Applied Mathematics 156 (8): 1308–1320, 2008.Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientations, and many other familiar structures. We find efficient solutions for several algorithmic problems on media: finding short reset sequences, shortest paths, testing whether a medium has a closed orientation, and listing the states of a medium given a black-box description.
Reference caching using unit distance redundant codes for activity reduction on address buses.
D. Eppstein and T. Givargis.
Worksh. Embedded System Codesign (ESCODES'02), San Jose, 2002, pp. 43–48.
J. Microprocessors & Microsystems 29 (4): 145–153, 2005.We study the problem of minimizing transitions in address signals on a bus. The UDRC part of the title refers to an algorithm for coding signals with at most one transition per signal (using an increased number of wires); we combine this with a scheme for caching previously coded addresses and use trace data to compare our technique with previous approaches.
Uninscribable four-regular polyhedron.
M. Dillencourt and D. Eppstein.
Electronic Geometry Models 2003.08.001.We find an example of a three-dimensional polyhedron, with four edges per vertex, that can not be placed in convex position with all vertices on the surface of a sphere.
The effect of faults on network expansion.
A. Bagchi, A. Bhargava, A. Chaudhary, D. Eppstein, and C. Scheideler.
arXiv:cs.DC/0404029.
16th ACM Symp. Parallelism in Algorithms and Architectures, Barcelona, 2004, pp. 286–293.
Theory of Computing Systems 39 (6): 903–928, 2006.Studies the resilience of distributed computation networks against adversarial and random fault models; shows that, in both models, certain networks can withstand constant fault probabilities and still contain a large subnetwork with similar expansion to the original.
The lattice dimension of a graph.
D. Eppstein.
arXiv:cs.DS/0402028.
Eur. J. Combinatorics 26 (6): 585–592, 2005.Describes a polynomial time algorithm for isometrically embedding graphs into an integer lattice of the smallest possible dimension. The technique involves maximum matching in an auxiliary graph derived from a partial cube representation of the input.
Comment on "Location-Scale Depth".
D. Eppstein.
J. Amer. Stat. Assoc. 99 (468): 976–979, 2004.Discusses a paper by Mizera and Müller on depth-based methods for simultaneously fitting both a center and a radius to a set of sample points, by viewing the points as lying on the boundary of a model of a higher dimensional hyperbolic space. Reformulates their method in combinatorial terms more likely to be familiar to computational geometers, and discusses the algorithmic implications of their work.
Approximate weighted farthest neighbors and minimum dilation stars.
J. Augustine, D. Eppstein, and K. Wortman.
arXiv:cs.CG/0602029.
Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam.
Springer, Lecture Notes in Comp. Sci. 6196, 2010, pp. 90–99.
Discrete Mathematics, Algorithms and Applications 2 (4): 553–565, 2010.The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space. This leads to fast approximation algorithms for the constrained minimum dilation star problem in any fixed dimension.
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.
Manhattan orbifolds.
D. Eppstein.
arXiv:math.MG/0612109.
Topology and its Applications 157 (2): 494–507, 2009.We investigate a class of metrics for 2-manifolds in which, except for a discrete set of singular points, the metric is locally isometric to an L1 metric, and show that with certain additional conditions such metrics are injective. We use this construction to find the tight span of squaregraphs and related graphs, and we find an injective metric that approximates the distances in the hyperbolic plane analogously to the way the rectilinear metrics approximate the Euclidean distance.
Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 637–648.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23 (2): 297–306, 2011.We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.
On verifying and engineering the well-gradedness of a union-closed family.
D. Eppstein, J.-C. Falmagne, and H. Uzun.
arXiv:0704.2919.
38th Meeting of the European Mathematical Psychology Group, Luxembourg, 2007.
J. Mathematical Psychology 53 (1): 34–39, 2009.We describe tests for whether the union-closure of a set family is well-graded, and algorithms for finding a minimal well-graded union-closed superfamily of a given set family.
Approximate Topological Matching of Quadrilateral Meshes.
D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
Proc. IEEE Int. Conf. Shape Modeling and Applications (SMI 2008), Stony Brook, New York, pp. 83–92.
The Visual Computer 25 (8): 771–783, 2009.We formalize problems of finding large approximately-matching regions of two related but not completely isomorphic quadrilateral meshes, show that these problems are NP-complete, and describe a natural greedy heuristic that is guaranteed to find good matches when the mismatching parts of the meshes are small.
(Preprint)
Motorcycle graphs: canonical quad mesh partitioning.
D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
Proc. 6th Symp. Geometry Processing, Copenhagen, Denmark, 2008.
Computer Graphics Forum 27 (5): 1477–1486, 2008.We use a construction inspired by the motorcycle graphs previously used in straight skeleton construction, to partition quadrilateral meshes into a small number of structured submeshes. Our construction is canonical in that two copies of the same mesh will always be partitioned in the same way, and can be used to speed up graph isomorphism computations for geometric models in feature animation.
Succinct greedy geometric routing using hyperbolic geometry.
D. Eppstein and M. T. Goodrich.
arXiv:0806.0341.
Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008
(under the different title "Succinct greedy graph drawing in the hyperbolic plane"),
Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 14–25.
IEEE Transactions on Computing 60 (11): 1571–1580, 2011.Greedy drawing is an idea for encoding network routing tables into the geometric coordinates of an embedding of the network, but most previous work in this area has ignored the space complexity of these encoded tables. We refine a method of R. Kleinberg for embedding arbitrary graphs into the hyperbolic plane, which uses linearly many bits to represent each vertex, and show that only logarithmic bits per point are needed.
Combinatorics and geometry of finite and infinite squaregraphs.
H.-J. Bandelt, V. Chepoi, and D. Eppstein.
arXiv:0905.4537.
SIAM J. Discrete Math. 24 (4): 1399–1440, 2010.Characterizes squaregraphs as duals of triangle-free hyperbolic line arrangements, provides a forbidden subgraph characterization of them, describes an algorithm for finding minimum subsets of vertices that generate the whole graph by medians, and shows that they may be isometrically embedded into Cartesian products of five (but not, in general, fewer than five) trees.
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.
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.
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.
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.
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)
Folding a paper strip to minimize thickness.
E. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno.
arXiv:1411.6371.
9th International Workshop on Algorithms and Computation (WALCOM 2015), Dhaka, Bangladesh.
Springer, Lecture Notes in Comp. Sci. 8973 (2015), pp. 113–124.
Journal of Discrete Algorithms 36: 18–26, 2016 (special issue for WALCOM).If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.
Structure of graphs with locally restricted crossings.
V. Dujmović, D. Eppstein, and D. R. Wood.
arXiv:1506.04380.
23rd Int. Symp. Graph Drawing, Los Angeles, California, 2015.
Springer, Lecture Notes in Comp. Sci. 9411 (2015), pp. 87–98.
SIAM J. Discrete Math. 31 (2): 805–824, 2017.The Graph Drawing version used the alternative title "Genus, treewidth, and local crossing number". We prove tight bounds on the treewidth of graphs embedded on low-genus surfaces with few crossings per edge, and nearly tight bounds on the number of crossings per edge for graphs with a given number of edges embedded on low-genus surfaces.
Grid peeling and the affine curve-shortening flow.
D. Eppstein, S. Har-Peled, and G. Nivasch.
arXiv:1710.03960.
Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 109–116.
Experimental Mathematics 29 (3): 306–316, 2020.We conjecture, based on experiments, that approximating a convex shape by the set of grid points inside it, for a fine enough grid, and then finding the convex layers of the resulting point set, produces curves that are close to those produced by affine curve-shortening, a continuous process on smooth curves.
Which women mathematicians get written about on Wikipedia, and why.
D. Eppstein.
AWM Newsletter 48 (4): 12–14, July–August 2018.This short opinion piece explains Wikipedia's guidelines for inclusion of articles on academics, and outlines steps to help improve Wikipedia's coverage of women in mathematics.
Minor-closed graph classes with bounded layered pathwidth.
V. Dujmović, D. Eppstein, G. Joret, P. Morin, and D. R. Wood.
arXiv:1810.08314.
SIAM J. Discrete Math 34 (3): 1693–1709, 2020.A minor-closed graph family has a functional relation between diameter and path width (bounded local pathwidth) if and only if it excludes an apex-tree. The same graph families are also the ones with bounded layered pathwidth: a simultaneous path decomposition and layering (sequence of subsets of vertices with all edges connecting the same subset or consecutive subsets) so that the intersection of a bag and a layer has constant size.
Some polycubes have no edge-unzipping.
E. Demaine, M. Demaine, D. Eppstein, and J. O'Rourke.
arXiv:1907.08433.
Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 101–105.
Geombinatorics 31 (3): 101–109, 2022.We find polycubes that cannot be cut along a simple path through their vertices and edges and unfolded to form a flat polygon in the plane.
On polyhedral realization with isosceles triangles.
D. Eppstein.
arXiv:2009.00116.
Graphs and Combinatorics 37 (4): 1247–1269, 2021.We find convex polyhedra with all faces triangular that cannot be realized with all faces isosceles, and new families of convex polyhedra with congruent isosceles-triangle faces.
Stack-number is not bounded by queue-number.
V. Dujmović, D. Eppstein, R. Robert Hickingbotham, P. Morin, and D. R. Wood.
arXiv:2011.04195.
Combinatorica 42: 151–164, 2022.Stack number is also known as page number or book thickness; it is the minimum number of stacks needed so that you can process the vertices of a graph in some sequence, pushing each edge onto one of the stacks when you process its first endpoint and popping it from the same stack when you process its second endpoint. Queue number is defined in the same way using queues instead of stacks. We show that the strong products of triangular grids and high-degree stars have bounded queue number but unbounded stack number. This result disproves the Blankenship–Oporowski conjecture, according to which subdividing edges of a graph a constant number of times cannot decrease its stack number from non-constant to constant, because subdivisions of the same products also have bounded stack number. It also confirms a conjecture of Bonnet et al on the existence of graphs with bounded sparse twin-width and unbounded stack number.
Multifold tiles of polyominoes and convex lattice polygons.
K. Chida, E. Demaine, M. Demaine, D. Eppstein, A. Hesterberg, T. Horiyama, J. Iacono, H. Ito, S. Langerman, R. Uehara, and Y. Uno.
23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021, pp. 28–29.
Thai Journal of Mathematics 21 (4): 957–978, 2023.We investigate shapes whose congruent copies can cover the plane exactly \(k\) times per point, but not a number of times that is a nonzero integer smaller than \(k\). We find polyominoes with this property for all \(k\ge 2\), and convex integer-coordinate polygons with this property for \(k=5\) and for all \(k\ge 7\).
Egyptian fractions with denominators from sequences closed under doubling.
D. Eppstein.
J. Integer Sequences 24: 21.8.8, 2021.
arXiv:2109.12217.We prove that if a set of positive integers includes multiples of all integers, and is closed under multiplication by two, then its reciprocals can form Egyptian fractions for every rational number up to the sum of reciprocals of the set.
The complexity of iterated reversible computation.
D. Eppstein.
arXiv:2112.11607.
Invited talk at 15th Latin American Theoretical Informatics Symposium, Guanajuato, Mexico, November 2022.
TheoretiCS 2: A10:1–A10:41, 2023.We study a class of problems involving computing a value \(f^{(n)}(x)\), the \(n\)th iterate of a function \(f\), for polynomial time bijections. We prove that these problems are complete for \(\mathsf{P}^{\mathsf{PSPACE}}\), and include hard problems in circuit complexity, graph algorithms, the simulation of one- and two-dimensional automata, and dynamical systems. We also provide a polynomial time algorithm for the special case where the bijection is an interval exchange transformation.
Product structure extension of the Alon–Seymour–Thomas theorem.
M. Distel, V. Dujmović, D. Eppstein, R. Robert Hickingbotham, G. Joret, P. Micek, P. Morin, M. T. Seweryn, and D. R. Wood.
arXiv:2212.08739.
SIAM J. Discrete Math. 38 (3): 2095–2107, 2024.The graphs in any nontrivial minor-closed graph family can be represented as strong products of a graph of treewidth 4 with a clique of size \(O(\sqrt{n})\). For planar graphs and \(K_{3,t}\)-minor-free graphs, the treewidth can be reduced to 2.
The widths of strict outerconfluent graphs.
D. Eppstein.
arXiv:2308.03967.
Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023 (poster session).
Springer, Lecture Notes in Computer Science 14466 (part II), pp. 244–247.
Discrete Mathematics & Theoretical Computer Science 26 (3) 20:1–20:17, 2024.We construct a family of strict outerconfluent graphs with unbounded clique-width. In contrast, we use a counting argument to prove that strict outerconfluent graphs have bounded twin-width.
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.
Computational complexities of folding.
D. Eppstein.
Invited talk, 8th International Meeting on Origami in Science, Mathematics and Education, Melbourne, Australia, 2024.
Invited talk, 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2024.
arXiv:2410.07666.
Journal of Information Processing 33: 954–973, 2025.We survey known hardness results on folding origami and prove several new ones: finding a flat-folded state is \(\mathsf{NP}\)-hard, but fixed-parameter tractable in a combination of ply and the treewidth of an associated graph. Finding a 3d-folded state cannot be expressed in closed form and cannot be computed by bounded-degree algebraic-root primitives. Reconfiguring certain systems of overlapping origami squares, hinged to a table at one edge, is \(\mathsf{PSPACE}\)-complete, and counting the number of configurations is \(\#\mathsf{P}\)-complete. Testing flat-foldability of infinite fractal folding patterns (even on normal square origami paper) is undecidable.
Noncrossing longest paths and cycles.
G. Aloupis, A. Biniaz, P. Bose, J.-L. De Carufel, D. Eppstein, A. Maheshwari, S. Odak, M. Smid, C. Tóth, and P. Valtr.
32nd International Symposium on Graph Drawing and Network Visualization.
Leibniz International Proceedings in Informatics (LIPIcs) 320, 2024, pp. 36:1–36:17.
arXiv:2410.05580.
Graphs and Combinatorics 41, article 122 (25pp), 2025.The shortest path or cycle through given planar points (the solution to the traveling salesperson problem) never crosses itself: any crossing can be eliminated by a local move that shortens the tour. One might think that, correspondingly, the longest path or cycle through enough planar points always crosses itself. We show that this is not the case: there exist arbitrarily large point sets for which the longest path or cycle has no crossing.
Princ-wiki-a mathematica: Wikipedia editing and mathematics.
D. Eppstein, J. B. Lewis, R. Woodroofe, and X. Easter.
arXiv:2412.20419.
Notices of the AMS 72 (1): 65–73, 2025.We describe the experience of editing mathematics articles on Wikipedia, with the aim of providing helpful advice for new editors and encouraging mathematicians to become Wikipedia editors.
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.