David Eppstein

research

∙ 07/20/2023

Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs

We study methods to manipulate weights in stress-graph embeddings to imp...

0 Alvin Chiu, et al. ∙

research

∙ 06/22/2023

Geometric Graphs with Unbounded Flip-Width

We consider the flip-width of geometric graphs, a notion of graph width ...

0 David Eppstein, et al. ∙

research

∙ 06/20/2023

A Parameterized Algorithm for Flat Folding

We prove that testing the flat foldability of an origami crease pattern ...

0 David Eppstein, et al. ∙

research

∙ 06/19/2023

Quasipolynomiality of the Smallest Missing Induced Subgraph

We study the problem of finding the smallest graph that does not occur a...

0 David Eppstein, et al. ∙

research

∙ 05/16/2023

Lower Bounds for Non-Adaptive Shortest Path Relaxation

We consider single-source shortest path algorithms that perform a sequen...

0 David Eppstein, et al. ∙

research

∙ 03/29/2023

On the complexity of embedding in graph products

Graph embedding, especially as a subgraph of a grid, is an old topic in ...

0 Therese Biedl, et al. ∙

research

∙ 03/01/2023

Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time

We show that, for planar point sets, the number of non-crossing Hamilton...

0 David Eppstein, et al. ∙

research

∙ 07/20/2022

Improved mixing for the convex polygon triangulation flip walk

We prove that the well-studied triangulation flip walk on a convex point...

0 David Eppstein, et al. ∙

research

∙ 06/26/2022

Locked and unlocked smooth embeddings of surfaces

We study the continuous motion of smooth isometric embeddings of a plana...

0 David Eppstein, et al. ∙

research

∙ 06/22/2022

Reflections in an octagonal mirror maze

Suppose we are given an environment consisting of axis-parallel and diag...

0 David Eppstein, et al. ∙

research

∙ 06/21/2022

Orthogonal dissection into few rectangles

We describe a polynomial time algorithm that takes as input a polygon wi...

0 David Eppstein, et al. ∙

research

∙ 03/24/2022

Geometric Dominating Sets

We consider a minimizing variant of the well-known No-Three-In-Line Prob...

0 Oswin Aichholzer, et al. ∙

research

∙ 02/10/2022

Three-dimensional graph products with unbounded stack-number

We prove that the stack-number of the strong product of three n-vertex p...

0 David Eppstein, et al. ∙

research

∙ 12/22/2021

The Complexity of Iterated Reversible Computation

We define a complexity class 𝖨𝖡 as the class of functional problems redu...

0 David Eppstein, et al. ∙

research

∙ 11/06/2021

Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs

We give a new rapid mixing result for a natural random walk on the indep...

0 David Eppstein, et al. ∙

research

∙ 10/12/2021

Finding Relevant Points for Nearest-Neighbor Classification

In nearest-neighbor classification problems, a set of d-dimensional trai...

0 David Eppstein, et al. ∙

research

∙ 08/17/2021

Limitations on Realistic Hyperbolic Graph Drawing

We show that several types of graph drawing in the hyperbolic plane requ...

0 David Eppstein, et al. ∙

research

∙ 07/08/2021

Angles of Arc-Polygons and Lombardi Drawings of Cacti

We characterize the triples of interior angles that are possible in non-...

0 David Eppstein, et al. ∙

research

∙ 06/29/2021

Optimal Spanners for Unit Ball Graphs in Doubling Metrics

Resolving an open question from 2006, we prove the existence of light-we...

0 David Eppstein, et al. ∙

research

∙ 05/11/2021

A Stronger Lower Bound on Parametric Minimum Spanning Trees

We prove that, for an undirected graph with n vertices and m edges, each...

0 David Eppstein, et al. ∙

research

∙ 01/25/2021

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

We investigate the parameterized complexity of finding subgraphs with he...

0 David Eppstein, et al. ∙

research

∙ 11/09/2020

Stack-number is not bounded by queue-number

We describe a family of graphs with queue-number at most 4 but unbounded...

0 Vida Dujmovic, et al. ∙

research

∙ 10/19/2020

The Graphs of Stably Matchable Pairs

We study the graphs formed from instances of the stable matching problem...

0 David Eppstein, et al. ∙

research

∙ 08/31/2020

On Polyhedral Realization with Isosceles Triangles

Answering a question posed by Joseph Malkevitch, we prove that there exi...

0 David Eppstein, et al. ∙

research

∙ 07/31/2020

New Results in Sona Drawing: Hardness and TSP Separation

Given a set of point sites, a sona drawing is a single closed curve, dis...

0 Man-Kwun Chiu, et al. ∙

research

∙ 07/28/2020

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra

We present new examples of topologically convex edge-ununfoldable polyhe...

0 Erik D. Demaine, et al. ∙

research

∙ 07/16/2020

Dynamic Products of Ranks

We describe a data structure that can maintain a dynamic set of points g...

0 David Eppstein, et al. ∙

research

∙ 05/01/2020

On the treewidth of Hanoi graphs

The objective of the well-known Towers of Hanoi puzzle is to move a set ...

0 David Eppstein, et al. ∙

research

∙ 04/17/2020

Low-stretch spanning trees of graphs with bounded width

We study the problem of low-stretch spanning trees in graphs of bounded ...

0 Glencora Borradaile, et al. ∙

research

∙ 02/14/2020

On the Edge Crossings of the Greedy Spanner

t-spanners are used to approximate the pairwise distances between a set ...

0 David Eppstein, et al. ∙

research

∙ 02/05/2020

Simplifying Activity-on-Edge Graphs

We formalize the simplification of activity-on-edge graphs used for visu...

0 David Eppstein, et al. ∙

research

∙ 10/13/2019

Face flips in origami tessellations

Given a flat-foldable origami crease pattern G=(V,E) (a straight-line dr...

0 Hugo A. Akitaya, et al. ∙

research

∙ 10/04/2019

C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width

For a clustered graph, i.e, a graph whose vertex set is recursively part...

0 Giordano Da Lozzo, et al. ∙

research

∙ 08/21/2019

Existence and hardness of conveyor belts

An open problem of Manuel Abellanas asks whether every set of disjoint c...

0 Molly Baird, et al. ∙

research

∙ 08/15/2019

Homotopy height, grid-major height and graph-drawing height

It is well-known that both the pathwidth and the outer-planarity of a gr...

0 Therese Biedl, et al. ∙

research

∙ 08/15/2019

Tracking Paths in Planar Graphs

We consider the NP-complete problem of tracking paths in a graph, first ...

0 David Eppstein, et al. ∙

research

∙ 06/11/2019

Bipartite and Series-Parallel Graphs Without Planar Lombardi Drawings

We find a family of planar bipartite graphs all of whose Lombardi drawin...

0 David Eppstein, et al. ∙

research

∙ 05/01/2019

Reconfiguring Undirected Paths

We consider problems in which a simple path of fixed length, in an undir...

0 Erik D. Demaine, et al. ∙

research

∙ 03/12/2019

Cubic Planar Graphs that cannot be Drawn on few Lines

For every integer ℓ, we construct a cubic 3-vertex-connected planar bipa...

0 David Eppstein, et al. ∙

research

∙ 03/12/2019

Counting Polygon Triangulations is Hard

We prove that it is #P-complete to count the triangulations of a (non-si...

0 David Eppstein, et al. ∙

research

∙ 02/19/2019

Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains

We show new applications of the nearest-neighbor chain algorithm, a tech...

0 Alon Efrat, et al. ∙

research

∙ 10/19/2018

Minor-closed graph classes with bounded layered pathwidth

We prove that a minor-closed class of graphs has bounded layered pathwid...

0 Vida Dujmovic, et al. ∙

research

∙ 10/17/2018

Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time

We consider decomposing a 3-connected planar graph G using laminar separ...

0 David Eppstein, et al. ∙

research

∙ 10/04/2018

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

0 David Eppstein, et al. ∙

research

∙ 08/17/2018

Realization and Connectivity of the Graphs of Origami Flat Foldings

We investigate the graphs formed from the vertices and creases of an ori...

0 David Eppstein, et al. ∙

research

∙ 08/07/2018

The Parameterized Complexity of Finding Point Sets with Hereditary Properties

We consider problems where the input is a set of points in the plane and...

0 David Eppstein, et al. ∙

research

∙ 08/01/2018

Geometric Fingerprint Recognition via Oriented Point-Set Pattern Matching

Motivated by the problem of fingerprint matching, we present geometric a...

0 David Eppstein, et al. ∙

research

∙ 05/14/2018

Quadratic Time Algorithms Appear to be Optimal for Sorting Evolving Data

We empirically study sorting in the evolving data model. In this model, ...

0 Juan Jose Besa, et al. ∙

research

∙ 05/10/2018

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

We consider the computational complexity of reconfiguration problems, in...

0 Jean Cardinal, et al. ∙

research

∙ 05/09/2018

Optimally Sorting Evolving Data

We give optimal sorting algorithms in the evolving data framework, where...

0 Juan Jose Besa, et al. ∙

David Eppstein

Featured Co-authors