David Eppstein

Univ. of California, Irvine, Donald Bren School of Information and Computer Sciences
http://www.ics.uci.edu/~eppstein/
eppstein@ics.uci.edu

Author, editor, or reviewer of:

• $K$ shortest paths and other “$K$ best” problems
• 3-coloring in time $O(1.3289^n)$
• 3-coloring in time $O(1.3446^n)$: a no-MIS algorithm
• A deterministic linear time algorithm for geometric separators and its applications
• A disk-packing algorithm for an origami magic trick
• A heuristic approach to program inversion
• A steady state model for graph power laws
• Acute square triangulation
• Algorithms for coloring quadtrees
• Algorithms for drawing media
• Algorithms for media
• Algorithms for proximity problems in higher dimensions
• Algorithms for weak epsilon-nets
• All maximal independent sets and dynamic dominance for sparse graphs
• An efficient algorithm for shortest paths in vertical and horizontal segments
• Approximate weighted farthest neighbors and minimum dilation stars
• Approximating center points with iterated Radon points
• Approximating the minimum weight Steiner triangulation
• Approximation algorithms for geometric problems
• Arboricity and bipartite subgraph listing algorithms
• Arrangements of polytopes and the 1-Steiner problem
• Asymptotic speed-ups in constructive solid geometry
• Average case analysis of dynamic geometric optimization
• Beta-skeletons have unbounded dilation
• Bibliography on $k$ shortest paths and other “$k$ best solutions” problems
• Choosing colors for geometric graphs via color space embeddings
• Choosing subsets with maximum weighted average
• Clustering for faster network simplex pivots
• Comment on Location-Scale Depth
• Computational complexity of games and puzzles
• Computing the depth of a flat
• Computing the discrepancy
• Computing the discrepancy with applications to supersampling patterns
• Confluent drawings: visualizing non-planar diagrams in a planar way
• Confluent layered drawings
• Connectivity, graph minors, and subgraph multiplicity
• Cubic partial cubes from simplicial arrangements
• Delta-confluent drawings
• Deterministic sampling and range counting in geometric data streams
• Diameter and treewidth in minor-closed graph families
• Dihedral bounds for mesh generation in high dimensions
• Dilation-free planar graphs
• Drawings of planar graphs with few slopes and segments
• Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees
• Dynamic connectivity in digital images
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Dynamic generators of topologically embedded graphs
• Dynamic graph algorithms
• Dynamic three-dimensional linear programming
• Edge insertion for optimal triangulation
• Edges and switches, tunnels and bridges
• Efficient algorithms for sequence analysis
• Efficient algorithms for sequence analysis with concave and convex gap costs
• Efficient algorithms with applications to molecular biology
• Efficient sequential and parallel algorithms for computing recovery points in trees and paths
• Emerging challenges in computational topology
• Equipartitions of graphs
• Fast approximation of centrality
• Fast hierarchical clustering and other applications of dynamic closest pairs
• Fast optimal parallel algorithms for maximal matching in sparse graphs
• Faster circle packing with application to nonobtuse triangulation
• Faster construction of planar two-centers
• Faster geometric $k$-point MST approximation
• Fat 4-polytopes and fatter 3-spheres
• Finding common ancestors and disjoint paths in DAGs
• Finding minimum area $k$-gons
• Finding short paths in small-world networks: when being intelligent requires being right only half the time
• Finding the $k$ shortest paths
• Finding the $k$ smallest spanning trees
• Flipping cubical meshes
• Flipping cubical meshes{}
• Geometric lower bounds for parametric matroid optimization
• Geometric thickness of complete graphs
• Geometry in Action
• Gliders in Life-like cellular automata
• Global optimization of mesh quality
• Guard placement for efficient point-in-polygon proofs
• Guest editor's forward to special issue for ACM Symp. on Computational Geometry
• Guest editor's forward to special issue of papers from the 34th Annual Symposium on Foundations of Computer Science
• Guest editor's forword to special issue on dynamic graph algorithms
• Happy endings for flip graphs
• Heesch's problem
• Hinged dissections of polyominoes and polyforms
• Hinged kite mirror dissection
• Horizon theorems for lines and polygons
• Hyperbolic geometry, Möbius transformations and geometric optimization
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction
• Improved bounds for intersecting triangles and halving planes
• Improved combinatorial group testing for real-world problem sizes
• Improved sparsification
• Incremental and decremental maintenance of planar width
• Interconnect criticality driven delay relaxation
• Internet packet filter management and rectangle geometry
• Iterated nearest neighbors and finding minimal polytopes
• Lazy algorithms for dynamic closest pair with arbitrary distance measures
• Lecture notes for ICS180, Winter 1997: Strategy and board game programming
• Lecture notes for ICS280, Spring 1999: Computational Statistics
• Linear complexity hexahedral mesh generation
• Maintenance of a minimum spanning forest in a dynamic planar graph
• Media Theory
• Memory reference caching for activity reduction on address buses
• Mesh generation and optimal triangulation
• Minimum dilation stars
• Minimum range balanced cuts via dynamic subset sums
• Möbius-invariant natural neighbor interpolation
• Multivariate regression depth
• New algorithms for minimum area $k$-gons
• New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams
• Nonrepetitive paths and cycles in graphs with application to Sudoku
• Offline algorithms for dynamic minimum spanning tree problems
• On nearest neighbor graphs
• On reset sequence length
• On the NP-completeness of cryptarithms
• On the number of minimal 1-Steiner trees
• On the parity of graph spanning tree numbers
• On triangulating three-dimensional polygons
• On verifying and engineering the well-gradedness of a union-closed family
• One-dimensional peg solitaire
• One-dimensional peg solitaire, and duotaire
• Optimal Möbius transformations for information visualization and meshing
• Optimal point placement for mesh smoothing
• Optimization over zonotopes and training support vector machines
• Optimized color gamuts for tiled displays
• Parallel algorithmic techniques for combinatorial computation
• Parallel construction of quadtrees and quality triangulations
• Parallel recognition of series parallel graphs
• Parametric and kinetic minimum spanning trees
• Persistence, offline algorithms, and space compaction
• Phutball endgames are hard
• Planar orientations with low out-degree and compaction of adjacency matrices
• Polynomial-size non-obtuse triangulation of polygons
• Preface to Festschrift for Zvi Galil
• Probabilistic and unambiguous computation are incomparable
• Provably good mesh generation
• Quadrilateral meshing by circle packing
• Quasiconvex analysis of backtracking algorithms
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• Quasiconvex programming
• Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions
• Re: Geometry problem: Optimal direction. Known results?
• Recognizing partial cubes in quadratic time
• Reference caching using unit distance redundant codes for activity reduction on address buses
• Regression depth and center points
• Representing all minimum spanning trees with applications to counting and generation
• Reset sequences for monotonic automata
• Searching for spaceships
• Selected open problems in graph drawing
• Separating geometric thickness from book thickness
• Separating thickness from geometric thickness
• Separator based sparsification for dynamic planar graph algorithms
• Separator based sparsification I: planarity testing and minimum spanning trees
• Separator based sparsification II: edge and vertex connectivity
• Sequence comparison with mixed convex and concave costs
• Sets of points with many halving lines
• Setting parameters by example
• Seventeen proofs of Euler's formula: $V-E+F=2$
• Shortest path along an MST
• Shortest paths in an arrangement with $k$ line orientations
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• Single triangle strip and loop on manifolds with boundaries
• Single-strip triangulation of manifolds with arbitrary topology
• Skip-webs: efficient distributed data structures for multi-dimensional data sets
• Small maximal independent sets and faster exact graph coloring
• Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters
• Spanning trees and spanners
• Sparse dynamic programming
• Sparse dynamic programming I: linear cost functions
• Sparse dynamic programming II: convex and concave cost functions
• Sparsification — A technique for speeding up dynamic graph algorithms
• Speeding up dynamic programming
• Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition
• Subgraph isomorphism in planar graphs and related problems
• Subquadratic nonobtuse triangulation of convex polygons
• Tangent spheres and triangle centers
• Ten algorithms for Egyptian fractions
• Testing bipartiteness of geometric intersection graphs
• The centroid of points with approximate weights
• The crust and the $\beta$-skeleton: combinatorial curve reconstruction
• The diameter of nearest neighbor graphs
• The distribution of cycle lengths in graphical models for iterative decoding
• The distribution of loop lengths in graphical models for turbo decoding
• The effect of faults on network expansion
• The expected extremes in a Delaunay triangulation
• The farthest point Delaunay triangulation minimizes angles
• The geometric thickness of low degree graphs
• The Geometry Junkyard: Inscribed square problem
• The Geometry Junkyard: Penrose tiling
• The Geometry Junkyard: Polyominoes and Other Animals
• The Geometry Junkyard: Zonohedra
• The lattice dimension of a graph
• The minimum expectation selection problem
• The skip quadtree: a simple dynamic data structure for multidimensional data
• The traveling salesman problem for cubic graphs
• The weighted maximum-mean subtree and other bicriterion subtree problems
• Three untetrahedralizable objects
• Tiling space and slabs with acute tetrahedra
• Tree-weighted neighbors and geometric $k$ smallest spanning trees
• Trees in \TeX
• Trees with convex faces and optimal angles
• Triangles and squares
• Triangulating polygons without large angles
• Uninscribable 4-regular polyhedron
• Ununfoldable polyhedra
• Ununfoldable polyhedra with convex faces
• Ununfoldable polyhedra with triangular faces
• Upright-quad drawing of $st$-planar learning spaces
• Using sparsification for parametric minimum spanning tree problems
• Vertex-unfoldings of simplicial manifolds
• Vertex-unfoldings of simplicial polyhedra
• Visibility with a moving point of view
• Worst-case bounds for subadditive geometric graphs
• Zonohedra and zonotopes