**Clustering for faster network simplex pivots**.

D. Eppstein.

Tech. Rep. 93-19, ICS, UCI, 1993.

*5th ACM-SIAM Symp. Discrete Algorithms,*Arlington, 1994, pp. 160–166.

*Networks*35 (3): 173–180, 2000.Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.

**Quadrilateral meshing by circle packing**.

M. Bern and D. Eppstein.

*2nd CGC Worksh. Computational Geometry*, Durham, North Carolina, 1997.

*6th Int. Meshing Roundtable,*Park City, Utah, 1997, pp. 7–19.

arXiv:cs.CG/9908016.

*Int. J. Comp. Geom. & Appl.*10 (4): 347–360, 2000.We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types:

- The elements form the cells of a Voronoi diagram,
- The elements each have two opposite 90 degree angles,
- All elements are kites, or
- All angles are at most 120 degrees.

*n*). The 120-degree bound is optimal; if a simply-connected region has all angles at least 120 degrees, any mesh of that region has a 120 degree angle.(BibTeX – Citations – CiteSeer)

**Fast hierarchical clustering and other applications of dynamic closest pairs**.

D. Eppstein.

*9th ACM-SIAM Symp. Discrete Algorithms,*San Francisco, 1998, pp. 619–628.

arXiv:cs.DS/9912014.

*J. Experimental Algorithmics*5 (1): 1–23, 2000.This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.

(Source code and experimental data – BibTeX – SODA paper – Citations – CiteSeer – ACM DL – JEA home page)

**Geometric thickness of complete graphs**.

M. Dillencourt, D. Eppstein, and D. S. Hirschberg.

*6th Int. Symp. Graph Drawing,*Montreal, August 1998.

Springer,*Lecture Notes in Comp. Sci.*1547, 1998, pp. 102–110.

arXiv:math.CO/9910185.

*J. Graph Algorithms and Applications*4 (3): 5–17, 2000 (special issue for GD98).We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.

(Springer abstract – BibTeX – CiteSeer – Citations – ACM DL – GDEA)

**Diameter and treewidth in minor-closed graph families**.

D. Eppstein.

arXiv:math.CO/9907126.

*Algorithmica*27: 275–291, 2000 (special issue on treewidth, graph minors, and algorithms).This paper introduces the

*diameter-treewidth property*(later known as*bounded local treewidth*): a functional relationship between the diameter of its graph and its treewidth. Previously known results imply that planar graphs have bounded local treewidth; we characterize the other minor-closed families with this property. Specifically, minor-closed family F has bounded local treewidth if and only if there exists an*apex graph*G that is not in F; an apex graph is a graph that can be made planar by removing a single vertex. The minor-free families that exclude an apex graph (and therefore have bounded local treewidth) include the bounded-genus graphs (for which, as with planar graphs, we show a linear bound for the treewidth as a function of the diameter) and K_{3,a}-free graphs. As a consequence, subgraph isomorphism for subgraphs of bounded size and approximations to several NP-hard optimization problems can be computed efficiently on these graphs, extending previous results for planar graphs.Some of these results were announced in the conference version of "subgraph isomorphism for planar graphs and related problems" but not included in the journal version. Since its publication, there have been many more works on local treewidth. The class of problems that could be solved quickly on graphs of bounded local treewidth was extended and classified by Frick and Grohe, "Deciding first-order properties of locally tree-decomposable structures",

*J. ACM*48: 1184–1206, 2001; the proof that bounded local treewidth is equivalent to having an excluded apex minor was simplified, and the dependence of the treewidth on diameter improved, by a subsequent paper of Demaine and Hajiaghayi, "Diameter and treewidth in minor-closed graph families, revisited",*Algorithmica*40: 211–215, 2004. The concept of local treewidth is the basis for the theory of*bidimensionality*, a general framework for fixed-parameter-tractable algorithms and approximation algorithms in minor-closed graph families; for a survey, see Demaine and Hajiaghayi, "The bidimensionality theory and its algorithmic applications",*The Computer J.*51: 292–302, 2008.**Incremental and decremental maintenance of planar width**.

D. Eppstein.

arXiv:cs.CG/9809038.

*10th ACM-SIAM Symp. Discrete Algorithms,*Baltimore, 1999, pp. S899-S900.

*J. Algorithms*37 (2): 570–577, 2000.We show how to maintain the width of a planar point set, subject to insertions or deletions (but not both) in time O(

*n*^{c}) per update for any*c*> 0. The idea is to apply our dynamic closest pair data structure to an appropriate measure of distance between pairs of convex hull features.(BibTeX – Citations – SODA talk slides – ACM DL)

**Regression depth and center points**.

N. Amenta, M. Bern, D. Eppstein, and S.-H. Teng.

arXiv:cs.CG/9809037.

*3rd CGC Worksh. Computational Geometry*, Brown Univ., 1998.

*Disc. Comp. Geom.*23 (3): 305–323, 2000.We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.

(BibTeX – Citations – CiteSeer)

**The distribution of cycle lengths in graphical models for iterative decoding**.

X. Ge, D. Eppstein, and P. Smyth.

arXiv:cs.DM/9907002.

Tech. Rep. 99-10, ICS, UCI, 1999.

IEEE Int. Symp. Information Theory, Sorrento, Italy, 2000.

*IEEE Trans. Information Theory*47 (6): 2549–2553, 2001.We compute the expected numbers of short cycles of each length in certain classes of random graphs used for turbocodes, estimate the probability that there are no such short cycles involving a given vertex, and experimentally verify our estimates. The scarcity of short cycles may help explain the empirically observed accuracy of belief-propagation based error-correction algorithms. Note, the TR, conference, and journal versions of this paper have slightly different titles.

(BibTeX – Citations: TR/ISIT – CiteSeer)

**Multivariate regression depth**.

M. Bern and D. Eppstein.

arXiv:cs.CG/9912013.

*16th ACM Symp. Comp. Geom.,*Hong Kong, 2000, pp. 315–321.

*Disc. Comp. Geom.*28 (1): 1–17, 2002.We generalize regression depth to k-flats. The k=0 case gives the classical notion of center points. We prove that for any set of n points in R

^{d}there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat. The full version of this paper also includes results from "Computing the Depth of a Flat".(BibTeX – SCG paper – Citations – CiteSeer)

**Searching for spaceships**.

D. Eppstein.

arXiv:cs.AI/0004003.

MSRI Combinatorial Game Theory Research Worksh., July 2000.

*More Games of No Chance*, R. J. Nowakowski, ed., MSRI Publications 42, pp. 433–453.We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state. Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.

(BibTeX – MSRI talk on streaming video and Slides – Citations – CiteSeer)

**Graphs for dynamic geometry**.

D. Eppstein.

Invited talk, Worksh. Dynamic Graph Algorithms, Victoria, Canada, 2000.This talk surveys work on computational geometry algorithms that use dynamic graph data structures, and the different kinds of geometric graph arising in this work.

**3-coloring in time O(1.3289^n)**.

R. Beigel and D. Eppstein.

arXiv:cs.DS/0006046.

*J. Algorithms*54:2 (2005) 168-204.Journal paper combining 3-coloring algorithms from our FOCS '95 paper with improved bounds from our SODA '01 paper.

**One-dimensional peg solitaire, and duotaire**.

C. Moore and D. Eppstein.

arXiv:math.CO/0006067 and math.CO/0008172.

MSRI Combinatorial Game Theory Research Worksh., July 2000.

Santa Fe Inst. working paper 00-09-050, September 2000.

*More Games of No Chance*, R. J. Nowakowski, ed., MSRI Publications 42, pp. 341–350.We describe by a regular expression the one-dimensional peg-solitaire positions reducible to a single peg, and provide a linear-time algorithm (based on finding shortest paths in an associated DAG) for reducing any such position to the minimum number of pegs. We then investigate impartial games in which players alternate peg solitaire moves in an attempt to be the one to move last.

(BibTeX – Citations – Cris' MSRI talk on streaming video – Cris' publications page – CiteSeer)

**Phutball endgames are hard**.

E. Demaine, M. Demaine, and D. Eppstein.

arXiv:cs.CC/0008025.

*More Games of No Chance*, R. J. Nowakowski, ed., MSRI Publications 42, pp. 351–360.We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.

(BibTeX – Citations – Erik's publications page – CiteSeer)

**Fast approximation of centrality**.

D. Eppstein and J. Wang.

arXiv:cs.DS/0009005.

*12th ACM-SIAM Symp. Discrete Algorithms,*Washington, 2001, pp. 228–229.

*J. Graph Algorithms & Applications*8 (1): 39–45, 2004.We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.

(BibTeX – SODA paper – Citations – CiteSeer)

**Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction**.

D. Eppstein.

arXiv:cs.DS/0009006.

*12th ACM-SIAM Symp. Discrete Algorithms,*Washington, 2001, pp. 329–337.Summarizes recent improvements to "3-Coloring in time O(1.3446

^{n}): a no-MIS algorithm". Merged with that paper for the journal version.(SODA talk slides – BibTeX – SODA paper – CiteSeer)

**Computing the depth of a flat**.

M. Bern and D. Eppstein.

arXiv:cs.CG/0009024.

*12th ACM-SIAM Symp. Discrete Algorithms,*Washington, 2001, pp. 700–701.We compute the regression depth of a k-flat in a set of n d-dimensional points, in time O(n

^{d-2}), an order of magnitude faster than the best known algorithms for computing the depth of a point or of a hyperplane. The results from this conference paper have been merged into the full version of "Multivariate Regression Depth".(SODA talk slides – SODA paper – BibTeX – Citations – CiteSeer)

**Internet packet filter management and rectangle geometry**.

D. Eppstein and S. Muthukrishnan.

arXiv:cs.CG/0010018.

*12th ACM-SIAM Symp. Discrete Algorithms,*Washington, 2001, pp. 827–835.Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n

^{3/2}) time algorithm for testing whether a rule set contains any ambiguities.(BibTeX – Citations – SODA paper – CiteSeer)

**Small maximal independent sets and faster exact graph coloring**.

D. Eppstein.

arXiv:cs.DS/0011009.

*7th Worksh. Algorithms and Data Structures,*Providence, Rhode Island, 2001.

Springer,*Lecture Notes in Comp. Sci.*2125, 2001, pp. 462–470.

*J. Graph Algorithms and Applications*(special issue for WADS'01) 7 (2): 131–140, 2003.We show that any graph can be colored in time O(2.415

^{n}), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.(BibTeX – Citations – CiteSeer – WADS talk slides – ACM DL)

Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.