
Angles of ArcPolygons and Lombardi Drawings of Cacti
We characterize the triples of interior angles that are possible in non...
read it

Optimal Spanners for Unit Ball Graphs in Doubling Metrics
Resolving an open question from 2006, we prove the existence of lightwe...
read it

A Stronger Lower Bound on Parametric Minimum Spanning Trees
We prove that, for an undirected graph with n vertices and m edges, each...
read it

Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes
We investigate the parameterized complexity of finding subgraphs with he...
read it

Stacknumber is not bounded by queuenumber
We describe a family of graphs with queuenumber at most 4 but unbounded...
read it

The Graphs of Stably Matchable Pairs
We study the graphs formed from instances of the stable matching problem...
read it

On Polyhedral Realization with Isosceles Triangles
Answering a question posed by Joseph Malkevitch, we prove that there exi...
read it

New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
read it

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra
We present new examples of topologically convex edgeununfoldable polyhe...
read it

Dynamic Products of Ranks
We describe a data structure that can maintain a dynamic set of points g...
read it

On the treewidth of Hanoi graphs
The objective of the wellknown Towers of Hanoi puzzle is to move a set ...
read it

Lowstretch spanning trees of graphs with bounded width
We study the problem of lowstretch spanning trees in graphs of bounded ...
read it

On the Edge Crossings of the Greedy Spanner
tspanners are used to approximate the pairwise distances between a set ...
read it

Simplifying ActivityonEdge Graphs
We formalize the simplification of activityonedge graphs used for visu...
read it

Face flips in origami tessellations
Given a flatfoldable origami crease pattern G=(V,E) (a straightline dr...
read it

CPlanarity Testing of Embedded Clustered Graphs with Bounded Dual CarvingWidth
For a clustered graph, i.e, a graph whose vertex set is recursively part...
read it

Existence and hardness of conveyor belts
An open problem of Manuel Abellanas asks whether every set of disjoint c...
read it

Homotopy height, gridmajor height and graphdrawing height
It is wellknown that both the pathwidth and the outerplanarity of a gr...
read it

Tracking Paths in Planar Graphs
We consider the NPcomplete problem of tracking paths in a graph, first ...
read it

Bipartite and SeriesParallel Graphs Without Planar Lombardi Drawings
We find a family of planar bipartite graphs all of whose Lombardi drawin...
read it

Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
read it

Cubic Planar Graphs that cannot be Drawn on few Lines
For every integer ℓ, we construct a cubic 3vertexconnected planar bipa...
read it

Counting Polygon Triangulations is Hard
We prove that it is #Pcomplete to count the triangulations of a (nonsi...
read it

Euclidean TSP, Motorcycle Graphs, and Other New Applications of NearestNeighbor Chains
We show new applications of the nearestneighbor chain algorithm, a tech...
read it

Minorclosed graph classes with bounded layered pathwidth
We prove that a minorclosed class of graphs has bounded layered pathwid...
read it

Finding Maximal Sets of Laminar 3Separators in Planar Graphs in Linear Time
We consider decomposing a 3connected planar graph G using laminar separ...
read it

Parameterized Leaf Power Recognition via Embedding into Graph Products
The kleaf power graph G of a tree T is a graph whose vertices are the l...
read it

Realization and Connectivity of the Graphs of Origami Flat Foldings
We investigate the graphs formed from the vertices and creases of an ori...
read it

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...
read it

Geometric Fingerprint Recognition via Oriented PointSet Pattern Matching
Motivated by the problem of fingerprint matching, we present geometric a...
read it

Quadratic Time Algorithms Appear to be Optimal for Sorting Evolving Data
We empirically study sorting in the evolving data model. In this model, ...
read it

Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
We consider the computational complexity of reconfiguration problems, in...
read it

Optimally Sorting Evolving Data
We give optimal sorting algorithms in the evolving data framework, where...
read it

StableMatching Voronoi Diagrams: Combinatorial Complexity and Algorithms
We study algorithms and combinatorial complexity bounds for stablematch...
read it

Making Change in 2048
The 2048 game involves tiles labeled with powers of two that can be merg...
read it

Faster Evaluation of Subtraction Games
Subtraction games are played with one or more heaps of tokens, with play...
read it

SubexponentialTime and FPT Algorithms for Embedded Flat Clustered Planarity
The CPlanarity problem asks for a drawing of a clustered graph, i.e., a...
read it

Reactive Proximity Data Structures for Graphs
We consider data structures for graphs where we maintain a subset of the...
read it

NC Algorithms for Perfect Matching and Maximum Flow in OneCrossingMinorFree Graphs
In 1988, Vazirani gave an NC algorithm for computing the number of perfe...
read it

Folding Polyominoes into (Poly)Cubes
We study the problem of folding a polyomino P into a polycube Q, allowin...
read it

Grid peeling and the affine curveshortening flow
In this paper we study an experimentallyobserved connection between two...
read it

SquareContact Representations of Partial 2Trees and Triconnected SimplyNested Graphs
A squarecontact representation of a planar graph G=(V,E) maps vertices ...
read it

Crossing Patterns in Nonplanar Road Networks
We define the crossing graph of a given embedded graph (such as a road n...
read it

The Effect of Planarization on Width
We study the effects of planarization (the construction of a planar diag...
read it

TriangleFree Penny Graphs: Degeneracy, Choosability, and Edge Count
We show that trianglefree penny graphs have degeneracy at most two, lis...
read it

Confluent Orthogonal Drawings of Syntax Diagrams
We provide a pipeline for generating syntax diagrams (also called railro...
read it

LinearTime Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings
We provide lineartime algorithms for geometric graphs with sublinearly ...
read it

SingleStrip Triangulation of Manifolds with Arbitrary Topology
Triangle strips have been widely used for efficient rendering. It is NP...
read it

Optimized Color Gamuts for Tiled Displays
We consider the problem of finding a large color space that can be gener...
read it

Searching for Spaceships
We describe software that searches for spaceships in Conway's Game of Li...
read it
David Eppstein
is this you? claim profile
Chancellor's Professor in the Computer Science Department of the University of California, Irvine.