- Parallel algorithmic techniques for combinatorial computation.
D. Eppstein and
Ann. Rev. Comput. Sci. 3: 233–283, 1988.
Invited talk by Z. Galil,
16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
Springer, Lecture Notes in Comp. Sci. 372, 1989, pp. 304–318.
This survey on parallel algorithms emphasized the use of basic
subroutines such as prefix sums, Euler tours, ear decomposition, and matrix
multiplication for solving more complicated graph problems.
ACM DL (ARCS) –
ACM DL (ICALP))
- Efficient algorithms for sequence analysis.
and G.F. Italiano.
International Advanced Workshop on
Sequences, Positano, Italy, 1991.
Sequences II: Methods in Communication, Security, and Computer Science,
R.M. Capocelli, A. De Santis, and U. Vaccaro, eds.,
Springer, 1993, pp. 225–244.
Surveys results on speeding up certain dynamic programs
used for sequence comparison and RNA structure prediction.
- Ten algorithms for Egyptian fractions.
Mathematica in Education and Research 4 (2): 5–15, 1995.
I survey and implement in Mathematica several methods
for representing rational numbers as sums of distinct unit fractions.
One of the methods involves searching for paths in a certain graph
using a k shortest paths heuristic.
in HTML and Mathematica notebook formats)
- Mesh generation and optimal triangulation.
and D. Eppstein.
Tech. Rep. CSL-92-1, Xerox PARC, 1992.
Computing in Euclidean Geometry,
D.-Z. Du and F.K. Hwang, eds.,
World Scientific, 1992, pp. 23–90.
version in Computing in Euclidean Geometry, 2nd ed.,
D.-Z. Du and F.K. Hwang, eds.,
World Scientific, 1995, pp. 47–123.
Considers both heuristics and theoretical algorithms
for finding good triangulations and tetrahedralizations
for surface interpolation and unstructured finite element meshes.
Note that the online copy here omits the figures;
also online is this paper's
- Approximation algorithms for geometric problems.
and D. Eppstein.
Approximation Algorithms for NP-hard Problems,
D. Hochbaum, ed.,
PWS Publishing, 1996, pp. 296–345.
Considers problems for which no polynomial-time exact algorithms
are known, and concentrates on bounds for worst-case approximation
ratios, especially those depending intrinsically on geometry
rather than on more general graph theoretic or metric space formulations.
Includes sections on the
traveling salesman problem,
minimum weight triangulation,
clustering, and separation problems.
- Spanning trees and spanners.
Tech. Rep. 96-16, ICS, UCI, 1996.
Handbook of Computational Geometry, J.-R. Sack and J. Urrutia,
eds., Elsevier, 1999, pp. 425–461.
Surveys results in geometric network design theory, including algorithms for
constructing minimum spanning trees and low-dilation graphs.
- Quasiconvex programming.
Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick,
Plenary talk at ALGO 2004,
Bergen, Norway, 2004.
Combinatorial and Computational Geometry, Goodman, Pach, and
Welzl, eds., MSRI Publications 52, 2005, pp. 287–331.
Defines quasiconvex programming, a form of generalized linear
programming in which one seeks the point minimizing the pointwise
maximum of a collection of quasiconvex functions.
Surveys algorithms for solving quasiconvex programs either numerically
or via generalizations of the dual simplex method from linear
programming, and describe varied applications of this geometric
optimization technique in meshing, scientific computation, information
visualization, automated algorithm analysis, and robust statistics.
(DIMACS talk slides –
ALGO talk slides)
- Selected open problems in graph drawing.
F. J. Brandenburg,
M. T. Goodrich,
S. G. Kobourov,
11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
Springer, Lecture Notes in
Comp. Sci. 2912, 2004, pp. 515–539.
We survey a number of open problems in theoretical and applied graph
- Geometry of partial cubes.
Invited talk at 6th Slovenian International Conference on Graph Theory,
Bled, Slovenia, 2007.
I survey some of my recent results on geometry of partial cubes, including
lattice dimension, graph drawing, cubic partial cubes, and partial cube
flip graphs of triangulations.
- Graph-theoretic solutions to computational geometry problems.
Invited talk at the 35th International
Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009),
Montpellier, France, 2009.
Springer, Lecture Notes in Comp. Sci. 5911, 2009, pp. 1–16.
We survey problems in computational geometry that may be solved by
constructing an auxiliary graph from the problem and solving a
graph-theoretic problem on the auxiliary graph. The problems considered
include the art gallery problem, partitioning into rectangles, minimum
diameter clustering, bend minimization in cartogram construction, mesh
stripification, optimal angular resolution, and metric embedding.
- Hyperconvexity and metric embedding.
William Rowan Hamilton Geometry and Topology Workshop,
Dublin, Ireland, 2009.
Invited talk at IPAM Workshop on Combinatorial Geometry, UCLA, 2009.
Surveys hyperconvex metric spaces, tight spans, and my work
orbifolds, tight span construction,
and optimal embedding into star metrics.
- Regular labelings and geometric structures.
Invited to 22nd Canadian Conference on Computational Geometry (CCCG 2010).
Invited to Proc. 21st International Symposium on Algorithms and Computation
(ISAAC 2010), Jeju, Korea, 2010.
Comp. Sci. 6506, 2010, p. 1.
We survey regular labelings for straight-line embedding of planar graphs
on grids, rectangular partitions, and orthogonal polyhedra, and the many
similarities between these different types of labeling.
(CCCG talk slides)