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