BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

David Eppstein

David Eppstein contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryData Structures and AlgorithmsDiscrete Mathematicsmath.COComputational Complexitymath.DG

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
21works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2025arXiv

Noncrossing Longest Paths and Cycles

Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Computational Complexities of Folding

We prove several hardness results on folding origami crease patterns. Flat-folding finite crease patterns is fixed-parameter tractable in the ply of the folded pattern (how many layers overlap at any point) and the treewidth of an associated cell adjacency graph. Under the exponential time hypothesis, the singly-exponential dependence of our algorithm on treewidth is necessary, even for bounded ply. Improving the dependence on ply would require progress on the unsolved map folding problem. Finding the shape of a polyhedron folded from a net with triangular faces and integer edge lengths is not possible in algebraic computation tree models of computation that at each tree node allow either the computation of arbitrary integer roots of real numbers, or the extraction of roots of polynomials with bounded degree and integer coefficients. For a model of reconfigurable origami with origami squares are attached at one edge by a hinge to a rigid surface, moving from one flat-folded state to another by changing the position of one square at a time is PSPACE-complete, and counting flat-folded states is #P-complete. For self-similar square crease patterns with infinitely many folds, testing flat-foldability is undecidable.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

On the complexity of embedding in graph products

Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph $G$ in a host graph that is the strong product of a path $P$ with a graph $H$ that satisfies some properties, such as having small treewidth, pathwidth or tree depth. We show that this is NP-hard, even under numerous restrictions on both $G$ and $H$. In particular, computing the row pathwidth and the row treedepth is NP-hard even for a tree of small pathwidth, while computing the row treewidth is NP-hard even for series-parallel graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reflections in an octagonal mirror maze

Suppose we are given an environment consisting of axis-parallel and diagonal line segments with integer endpoints, each of which may be reflective or non-reflective, with integer endpoints, and an initial position for a light ray passing through points of the integer grid. Then in time polynomial in the number of segments and in the number of bits needed to specify the coordinates of the input, we can determine the eventual fate of the reflected ray.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes

We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph $G$, a non-trivial hereditary property $Π$ and an integer parameter $k$, the general problem $P(G,Π,k)$ asks whether there exists $k$ vertices of $G$ that induce a subgraph satisfying property $Π$. This problem, $P(G,Π,k)$ has been proved to be NP-complete by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be W[1]-complete by Khot and Raman, if $Π$ includes all trivial graphs but not all complete graphs and vice versa; and is fixed-parameter tractable (FPT), otherwise. As the problem is W[1]-complete on general graphs when $Π$ includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes. Motivated by this line of research, we study the problem on graphs which also belong to a hereditary graph class and establish a framework which settles the parameterized complexity of the problem for various hereditary graph classes. In particular, we show that: $P(G,Π,k)$ is solvable in polynomial time when the graph $G$ is co-bipartite and $Π$ is the property of being planar, bipartite or triangle-free (or vice-versa). $P(G,Π,k)$ is FPT when the graph $G$ is planar, bipartite or triangle-free and $Π$ is the property of being planar, bipartite or triangle-free, or graph $G$ is co-bipartite and $Π$ is the property of being co-bipartite. $P(G,Π,k)$ is W[1]-complete when the graph $G$ is $C_4$-free, $K_{1,4}$-free or a unit disk graph and $Π$ is the property of being either planar or bipartite.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra

We present new examples of topologically convex edge-ununfoldable polyhedra, i.e., polyhedra that are combinatorially equivalent to convex polyhedra, yet cannot be cut along their edges and unfolded into one planar piece without overlap. One family of examples is acutely triangulated, i.e., every face is an acute triangle. Another family of examples is stacked, i.e., the result of face-to-face gluings of tetrahedra. Both families achieve another natural property, which we call very ununfoldable: for every $k$, there is an example such that every nonoverlapping multipiece edge unfolding has at least $k$ pieces.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Low-stretch spanning trees of graphs with bounded width

We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$. Our proof implies a linear time algorithm for sampling from $\mathcal T$. Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$. For graphs of cutwidth $c$, we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the treewidth of Hanoi graphs

The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Parameterized Leaf Power Recognition via Embedding into Graph Products

The $k$-leaf power graph $G$ of a tree $T$ is a graph whose vertices are the leaves of $T$ and whose edges connect pairs of leaves at unweighted distance at most~$k$ in $T$. Recognition of the $k$-leaf power graphs for $k \geq 7$ is still an open problem. In this paper, we provide two algorithms for this problem for sparse leaf power graphs. Our results shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by $k$ and by the degeneracy of the given graph. To prove this, we first describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of $k$ and the degeneracy of $G$. The first presented algorithm uses methods based on monadic second-order logic (MSO$_2$) to recognize the existence of a leaf power as a subgraph of the product graph. Using the same embedding in the product graph, the second algorithm presents a dynamic programming approach to solve the problem and provide a better dependence on the parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reactive Proximity Data Structures for Graphs

We consider data structures for graphs where we maintain a subset of the nodes called sites, and allow proximity queries, such as asking for the closest site to a query node, and update operations that enable or disable nodes as sites. We refer to a data structure that can efficiently react to such updates as reactive. We present novel reactive proximity data structures for graphs of polynomial expansion, i.e., the class of graphs with small separators, such as planar graphs and road networks. Our data structures can be used in several logistical problems and geographic information systems dealing with real-time data, such as emergency dispatching. We experimentally compare our data structure to Dijkstra's algorithm in a system emulating random queries in a real road network.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simplifying Activity-on-Edge Graphs

We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges represent either tasks of the project or timing constraints between milestones. In this framework, a timeline of the project can be constructed as a leveled drawing of the graph, where the levels of the vertices represent the time at which each milestone is scheduled to happen. We focus on the following problem: given an activity-on-edge graph representing a project, find an equivalent activity-on-edge graph (one with the same critical paths) that has the minimum possible number of milestone vertices among all equivalent activity-on-edge graphs. We provide a polynomial-time algorithm for solving this graph minimization problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

We study algorithms and combinatorial complexity bounds for \emph{stable-matching Voronoi diagrams}, where a set, $S$, of $n$ point sites in the plane determines a stable matching between the points in $\mathbb{R}^2$ and the sites in $S$ such that (i) the points prefer sites closer to them and sites prefer points closer to them, and (ii) each site has a quota or "appetite" indicating the area of the set of points that can be matched to it. Thus, a stable-matching Voronoi diagram is a solution to the well-known post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work on the stable-matching Voronoi diagram provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. In this paper, we show that a stable-matching Voronoi diagram of $n$ point sites has $O(n^{2+\varepsilon})$ faces and edges, for any $\varepsilon>0$, and show that this bound is almost tight by giving a family of diagrams with $Θ(n^2)$ faces and edges. We also provide a discrete algorithm for constructing it in $O(n^3\log n+n^2f(n))$ time in the real-RAM model of computation, where $f(n)$ is the runtime of a geometric primitive (which we define) that can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation. We show, however, how to compute the geometric primitive exactly for polygonal convex distance functions.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Face flips in origami tessellations

Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $μ:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $F$ of $G$ to create a new MV assignment $μ_F$ which equals $μ$ except for all creases $e$ bordering $F$, where we have $μ_F(e)=-μ(e)$. In this paper we explore the configuration space of face flips for a variety of crease patterns $G$ that are tilings of the plane, proving examples where $μ_F$ results in a MV assignment that is either never, sometimes, or always flat-foldable for various choices of $F$. We also consider the problem of finding, given two foldable MV assignments $μ_1$ and $μ_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $μ_1$ into $μ_2$. We find polynomial-time algorithms for this in the cases where $G$ is either a square grid or the Miura-ori, and show that this problem is NP-hard in the case where $G$ is the triangle lattice.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Grid peeling and the affine curve-shortening flow

In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. The first one (which we call "grid peeling") is the convex-layer decomposition of subsets $G\subset \mathbb Z^2$ of the integer grid, previously studied for the particular case $G=\{1,\ldots,m\}^2$ by Har-Peled and Lidický (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (1993) and Sapiro and Tannenbaum (1993). We present empirical evidence that, in a certain well-defined sense, grid peeling behaves at the limit like ACSF on convex curves. We offer some theoretical arguments in favor of this conjecture. We also pay closer attention to the simple case where $G=\mathbb N^2$ is a quarter-infinite grid. This case corresponds to ACSF starting with an infinite L-shaped curve, which when transformed using the ACSF becomes a hyperbola for all times $t>0$. We prove that, in the grid peeling of $\mathbb N^2$, (1) the number of grid points removed up to iteration $n$ is $Θ(n^{3/2}\log n)$; and (2) the boundary at iteration $n$ is sandwiched between two hyperbolas that are separated from each other by a constant factor.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect

We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary transformations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration and sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems: $\bullet$ Given two satisfying assignments to a planar monotone instance of Not-All-Equal 3-SAT, can one assignment be transformed into the other by single variable `flips' (assignment changes), preserving satisfiability at every step? $\bullet$ Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? $\bullet$ Given two points in $\{0,1\}^n$ contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the instances of the NP problems that appear as input to the reconfiguration problems in our reductions can be shown to lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximate Greedy Clustering and Distance Selection for Graph Metrics

$\newcommand{\eps}{\varepsilon}$ In this paper, we consider two important problems defined on finite metric spaces, and provide efficient new algorithms and approximation schemes for these problems on inputs given as graph shortest path metrics or high-dimensional Euclidean metrics. The first of these problems is the greedy permutation (or farthest-first traversal) of a finite metric space: a permutation of the points of the space in which each point is as far as possible from all previous points. We describe randomized algorithms to find $(1+\eps)$-approximate greedy permutations of any graph with $n$ vertices and $m$ edges in expected time $O(\eps^{-1}(m+n)\log n\log(n/\eps))$, and to find $(1+\eps)$-approximate greedy permutations of points in high-dimensional Euclidean spaces in expected time $O(\eps^{-2} n^{1+1/(1+\eps)^2 + o(1)})$. Additionally we describe a deterministic algorithm to find exact greedy permutations of any graph with $n$ vertices and treewidth $O(1)$ in worst-case time $O(n^{3/2}\log^{O(1)} n)$. The second of the two problems we consider is distance selection: given $k \in [ \binom{n}{2} ]$, we are interested in computing the $k$th smallest distance in the given metric space. We show that for planar graph metrics one can approximate this distance, up to a constant factor, in near linear time.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Treetopes and their Graphs

We define treetopes, a generalization of the three-dimensional roofless polyhedra (Halin graphs) to arbitrary dimensions. Like roofless polyhedra, treetopes have a designated base facet such that every face of dimension greater than one intersects the base in more than one point. We prove an equivalent characterization of the 4-treetopes using the concept of clustered planarity from graph drawing, and we use this characterization to recognize the graphs of 4-treetopes in polynomial time. This result provides one of the first classes of 4-polytopes, other than pyramids and stacked polytopes, that can be recognized efficiently from their graphs.

0 citations0 reviewsNo code linkedOpen access