David Eppstein

@misc{cs.DS/0006046,
  title = {{3-coloring in time $O(1.3289^n)$}},
  author = {Richard Beigel and David Eppstein},
  eprint = {cs.DS/0006046},
  howpublished = {ACM Computing Research Repository},
  month = {June},
  year = {2000}}

@article{BeiEpp-Algs-05,
  title = {{3-coloring in time $O(1.3289^n)$}},
  author = {Richard Beigel and David Eppstein},
  eprint = {cs.DS/0006046},
  journal = {J. Algorithms},
  volume = {54},
  number = {2},
  pages = {168--204},
  month = {February},
  year = {2005},
  url = {http://dx.doi.org/10.1016/j.jalgor.2004.06.008}}

@techreport{BeiEpp-ECCC-95,
  title = {{3-coloring in time $O(1.3446^n)$: a no-MIS algorithm}},
  author = {Richard Beigel and David Eppstein},
  institution = {Electronic Colloq. on Computational Complexity},
  number = {TR95-033},
  year = {1995},
  url = {ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1995/TR95-033/index.html}}

@inproceedings{BeiEpp-FOCS-95,
  title = {{3-coloring in time $O(1.3446^n)$: a no-MIS algorithm}},
  author = {Richard Beigel and David Eppstein},
  booktitle = {Proc. 36th Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {444--453},
  month = {October},
  year = {1995}}

@inproceedings{EppMilTen-SCG-93,
  title = {{A deterministic linear time algorithm for geometric separators
    and its applications}},
  author = {David Eppstein and Gary L. Miller and Shang-Hua Teng},
  booktitle = {Proc. 9th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {99--108},
  month = {May},
  year = {1993},
  url = {http://www.acm.org/pubs/citations/proceedings/compgeom/160985/p99-eppstein/}}

@article{EppMilTen-FI-95,
  title = {{A deterministic linear time algorithm for geometric separators
    and its applications}},
  author = {David Eppstein and Gary L. Miller and Shang-Hua Teng},
  journal = {Fundamenta Informaticae},
  publisher = {Eur. Assoc. for Theoretical Computer Science},
  series = {Annales Societatis Mathematicae Polonae, ser. IV},
  volume = {22},
  number = {4},
  pages = {309--331},
  month = {April},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/EppMilTen-FI-95.ps.gz},
  note = {Special issue on computational geometry},
  review = {MR-96m:68162}}

@article{MR-96m:68162,
  reviews = {EppMilTen-FI-95},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{A deterministic linear time algorithm for geometric separators
    and its applications}},
  author = {Jovi{\v{s}}a {\v{Z}}uni{\'c}},
  number = {96m:68162},
  year = {1996}}

@inproceedings{BerDemEpp-Fun-98,
  title = {{A disk-packing algorithm for an origami magic trick}},
  author = {Marshall Wayne Bern and Erik D. Demaine and David Eppstein and
    Barry Hayes},
  booktitle = {Proc. Int. Conf. Fun with Algorithms, Elba, 1998},
  number = {4},
  editor = {Elena Lodi and Linda Pagli and Nicola Santoro},
  series = {Proceedings in Informatics},
  publisher = {Carleton Scientific},
  address = {Waterloo, CANADA},
  pages = {32--42},
  year = {1999},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerDemEpp-Fun-98.ps.gz}}

@inproceedings{BerDemEpp-Ori-02,
  title = {{A disk-packing algorithm for an origami magic trick}},
  author = {Marshall Wayne Bern and Erik D. Demaine and David Eppstein and
    Barry Hayes},
  booktitle = {Origami$^3$: Proc. 3rd Int. Mtg. Origami Science, Math, and
    Education (3OSME), Asilomar, Calif., 2001},
  publisher = {A K Peters},
  editor = {Thomas Hull},
  pages = {17--28},
  year = {2002},
  review = {MR-2004b:52030}}

@article{MR-2004b:52030,
  reviews = {BerDemEpp-Ori-02},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{A disk-packing algorithm for an origami magic trick}},
  author = {Uwe Schnell},
  number = {2004b:52030},
  year = {2004},
  text = {
     The problem of folding a sheet of paper so that a single straight cut
    produces a cut-out of a certain figure can be formulated mathematically
    as follows: Given a polygon with holes $P$ and a rectangle $R \supset
    P$, find a flat-folding of $R$ such that the cross-section of the folding
    with a perpendicular plane is the boundary of $P$. The authors give an
    algorithm to solve this problem. The strategy is to pack disks such that
    the disk centers induce a mixed triangulation/quadrangulation respecting
    the boundary of the polygon. The algorithm is based on results by R.
    J. Lang [in Proceedings of the twelfth annual symposium on computational
    geometry (Philadelphia, PA, 1996), 98--105, ACM, NY, 1996] and M. W.
    Bern and D. Eppstein \ref[Internat. J. Comput. Geom. Appl.  2 (1992),
    no. 3, 241--255; MR1194449 (94e:52016a)].}}

@inproceedings{Epp-IJCAI-85,
  title = {{A heuristic approach to program inversion}},
  author = {David Eppstein},
  booktitle = {Proc. 9th Int. Joint Conf. Artificial Intelligence},
  volume = {1},
  pages = {219-221},
  month = {August},
  year = {1985},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-IJCAI-85.pdf}}

@misc{cs.DM/0204001,
  title = {{A steady state model for graph power laws}},
  author = {David Eppstein and Joseph Yannkae Wang},
  eprint = {cs.DM/0204001},
  howpublished = {ACM Computing Research Repository},
  month = {April},
  year = {2002}}

@inproceedings{EppWan-WWW-02,
  title = {{A steady state model for graph power laws}},
  author = {David Eppstein and Joseph Yannkae Wang},
  eprint = {cs.DM/0204001},
  booktitle = {2nd Int. Worksh. Web Dynamics},
  month = {May},
  year = {2002}}

@misc{Epp-acute-square,
  title = {{Acute square triangulation}},
  author = {David Eppstein},
  howpublished = {web page},
  month = {July},
  year = {1997},
  url = {http://www.ics.uci.edu/~eppstein/junkyard/acute-square/}}

@misc{cs.CG/9907030,
  title = {{Algorithms for coloring quadtrees}},
  author = {Marshall Wayne Bern and David Eppstein and Brad Hutchings},
  eprint = {cs.CG/9907030},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {1999}}

@article{BerEppHut-Algo-02,
  title = {{Algorithms for coloring quadtrees}},
  author = {Marshall Wayne Bern and David Eppstein and Brad Hutchings},
  eprint = {cs.CG/9907030},
  journal = {Algorithmica},
  volume = {32},
  number = {1},
  pages = {87--94},
  month = {January},
  year = {2002},
  review = {MR-2002h:68036}}

@article{MR-2002h:68036,
  reviews = {BerEppHut-Algo-02},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Algorithms for coloring quadtrees}},
  number = {2002h:68036},
  year = {2002}}

@inproceedings{Epp-GD-04,
  title = {{Algorithms for drawing media}},
  author = {David Eppstein},
  eprint = {cs.DS/0406020},
  booktitle = {Proc. 12th Int. Symp. Graph Drawing (GD 2004)},
  number = {3383},
  editor = {J{\'a}nos Pach},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {173--183},
  year = {2004}}

@misc{cs.DS/0406020,
  title = {{Algorithms for drawing media}},
  author = {David Eppstein},
  eprint = {cs.DS/0406020},
  howpublished = {ACM Computing Research Repository},
  month = {June},
  year = {2004}}

@misc{cs.DS/0206033,
  title = {{Algorithms for media}},
  author = {David Eppstein and Jean-Claude Falmagne},
  eprint = {cs.DS/0206033},
  howpublished = {ACM Computing Research Repository},
  month = {June},
  year = {2002}}

@article{DicEpp-CGTA-96,
  title = {{Algorithms for proximity problems in higher dimensions}},
  author = {Matthew T. Dickerson and David Eppstein},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {5},
  number = {5},
  pages = {277--291},
  month = {January},
  year = {1996},
  url = {http://dx.doi.org/10.1016/0925-7721(95)00009-7},
  review = {MR-96m:68180}}

@article{MR-96m:68180,
  reviews = {DicEpp-CGTA-96},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Algorithms for proximity problems in higher dimensions}},
  number = {96m:68180},
  year = {1996}}

@misc{cs.DS/0407036,
  title = {{All maximal independent sets and dynamic dominance for sparse
    graphs}},
  author = {David Eppstein},
  eprint = {cs.DS/0407036},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2004}}

@inproceedings{Epp-SODA-05,
  title = {{All maximal independent sets and dynamic dominance for sparse
    graphs}},
  author = {David Eppstein},
  eprint = {cs.DS/0407036},
  booktitle = {Proc. 16th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {451--459},
  month = {January},
  year = {2005}}

@inproceedings{EppHar-WADS-97,
  title = {{An efficient algorithm for shortest paths in vertical and horizontal
    segments}},
  author = {David Eppstein and David Hart},
  booktitle = {Proc. 5th Worksh. Algorithms and Data Structures (WADS 1997)},
  number = {1272},
  editor = {Frank K. H. A. Dehne and Andrew Rau-Chaplin and J{\"o}rg-Rudiger
    Sack and Roberto Tamassia},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {234--247},
  month = {August},
  year = {1997}}

@inproceedings{ClaEppMil-SCG-93,
  title = {{Approximating center points with iterated Radon points}},
  author = {Kenneth L. Clarkson and David Eppstein and Gary L. Miller and
    Carl Sturtivant and Shang-Hua Teng},
  booktitle = {Proc. 9th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {91--98},
  month = {May},
  year = {1993}}

@article{ClaEppMil-IJCGA-96,
  title = {{Approximating center points with iterated Radon points}},
  author = {Kenneth L. Clarkson and David Eppstein and Gary L. Miller and
    Carl Sturtivant and Shang-Hua Teng},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {6},
  number = {3},
  pages = {357--377},
  month = {September},
  year = {1996},
  note = {Special issue for 9th SCG},
  review = {MR-97h:65010}}

@article{MR-97h:65010,
  reviews = {ClaEppMil-IJCGA-96},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Approximating center points with iterated Radon points}},
  number = {97h:65010},
  year = {1997}}

@techreport{Epp-TR-91-55,
  title = {{Approximating the minimum weight Steiner triangulation}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {91-55},
  year = {1991},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-91-55.pdf}}

@inproceedings{Epp-SODA-92-mwst,
  title = {{Approximating the minimum weight Steiner triangulation}},
  author = {David Eppstein},
  booktitle = {Proc. 3rd Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {48--57},
  month = {January},
  year = {1992},
  review = {MR-93e:68099}}

@article{MR-93e:68099,
  reviews = {Epp-SODA-92-mwst},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Approximating the minimum weight Steiner triangulation}},
  number = {93e:68099},
  year = {1993}}

@article{Epp-DCG-94,
  title = {{Approximating the minimum weight Steiner triangulation}},
  author = {David Eppstein},
  journal = {Discrete {\&} Computational Geometry},
  volume = {11},
  number = {2},
  pages = {163--191},
  year = {1994},
  review = {MR-95e:68218}}

@article{MR-95e:68218,
  reviews = {Epp-DCG-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Approximating the minimum weight Steiner triangulation}},
  author = {Helmut Alt},
  number = {95e:68218},
  year = {1995}}

@incollection{BerEpp-AA-96,
  title = {{Approximation algorithms for geometric problems}},
  author = {Marshall Wayne Bern and David Eppstein},
  booktitle = {Approximation Algorithms for NP-hard Problems},
  publisher = {PWS Publishing},
  editor = {Dorit Hochbaum},
  pages = {296--345},
  year = {1996},
  chapter = {8}}

@techreport{Epp-TR-94-11,
  title = {{Arboricity and bipartite subgraph listing algorithms}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {94-11},
  year = {1994},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-11.pdf}}

@article{Epp-IPL-94,
  title = {{Arboricity and bipartite subgraph listing algorithms}},
  author = {David Eppstein},
  journal = {Information Processing Letters},
  volume = {51},
  number = {4},
  pages = {207--211},
  month = {August},
  year = {1994},
  url = {http://dx.doi.org/10.1016/0020-0190(94)90121-X},
  review = {MR-95j:05157}}

@article{MR-95j:05157,
  reviews = {Epp-IPL-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Arboricity and bipartite subgraph listing algorithms}},
  author = {Fabrizio Luccio},
  number = {95j:05157},
  year = {1995}}

@techreport{Epp-TR-92-87,
  title = {{Asymptotic speed-ups in constructive solid geometry}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-87},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-87.pdf}}

@article{Epp-Algo-95,
  title = {{Asymptotic speed-ups in constructive solid geometry}},
  author = {David Eppstein},
  journal = {Algorithmica},
  volume = {13},
  number = {5},
  pages = {462--471},
  month = {May},
  year = {1995},
  review = {MR-96b:68177}}

@article{MR-96b:68177,
  reviews = {Epp-Algo-95},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Asymptotic speed-ups in constructive solid geometry}},
  number = {96b:68177},
  year = {1996}}

@techreport{Epp-TR-93-18,
  title = {{Average case analysis of dynamic geometric optimization}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {93-18},
  month = {15 April},
  year = {1993}}

@inproceedings{Epp-SODA-94-dyngeom,
  title = {{Average case analysis of dynamic geometric optimization}},
  author = {David Eppstein},
  booktitle = {Proc. 5th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {77--86},
  month = {January},
  year = {1994},
  review = {MR-95b:90143}}

@article{MR-95b:90143,
  reviews = {Epp-SODA-94-dyngeom},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Average case analysis of dynamic geometric optimization}},
  number = {95b:90143},
  year = {1995}}

@article{Epp-CGTA-96,
  title = {{Average case analysis of dynamic geometric optimization}},
  author = {David Eppstein},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {6},
  number = {1},
  pages = {45--68},
  month = {April},
  year = {1996},
  url = {http://dx.doi.org/10.1016/0925-7721(95)00018-6},
  review = {MR-97a:90104}}

@article{MR-97a:90104,
  reviews = {Epp-CGTA-96},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Average case analysis of dynamic geometric optimization}},
  author = {Xue Liang Li},
  number = {97a:90104},
  year = {1997}}

@techreport{Epp-TR-96-15,
  title = {{Beta-skeletons have unbounded dilation}},
  author = {David Eppstein},
  eprint = {cs.CG/9907031},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {96-15},
  year = {1996},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-15.pdf}}

@misc{cs.CG/9907031,
  title = {{Beta-skeletons have unbounded dilation}},
  author = {David Eppstein},
  eprint = {cs.CG/9907031},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {1999}}

@article{Epp-CGTA-02,
  title = {{Beta-skeletons have unbounded dilation}},
  author = {David Eppstein},
  eprint = {cs.CG/9907031},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {23},
  number = {1},
  pages = {43--52},
  month = {July},
  year = {2002},
  url = {http://dx.doi.org/10.1016/S0925-7721(01)00055-4},
  review = {MR-2004a:05045}}

@article{MR-2004a:05045,
  reviews = {Epp-CGTA-02},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Beta-skeletons have unbounded dilation}},
  number = {2004a:05045},
  year = {2004}}

@techreport{EppHir-TR-95,
  title = {{Choosing subsets with maximum weighted average}},
  author = {David Eppstein and Daniel S. Hirschberg},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-12},
  year = {1995}}

@inproceedings{EppHir-MSI-95,
  title = {{Choosing subsets with maximum weighted average}},
  author = {David Eppstein and Daniel S. Hirschberg},
  booktitle = {Proc. 5th Worksh. Computational Geometry},
  organization = {Army Research Office; State Univ. of New York at Stony
    Brook, Mathematical Sciences Inst.},
  pages = {7--8},
  month = {October},
  year = {1995}}

@article{EppHir-Algs-97,
  title = {{Choosing subsets with maximum weighted average}},
  author = {David Eppstein and Daniel S. Hirschberg},
  journal = {J. Algorithms},
  volume = {24},
  number = {1},
  pages = {177--193},
  month = {July},
  year = {1997},
  url = {http://dx.doi.org/10.1006/jagm.1996.0849}}

@techreport{Epp-TR-93-19,
  title = {{Clustering for faster network simplex pivots}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {93-19},
  month = {15 April},
  year = {1993}}

@inproceedings{Epp-SODA-94-simplex,
  title = {{Clustering for faster network simplex pivots}},
  author = {David Eppstein},
  booktitle = {Proc. 5th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {160--166},
  month = {January},
  year = {1994},
  review = {MR-95b:90142}}

@article{MR-95b:90142,
  reviews = {Epp-SODA-94-simplex},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Clustering for faster network simplex pivots}},
  number = {95b:90142},
  year = {1995}}

@article{Epp-Nw-00,
  title = {{Clustering for faster network simplex pivots}},
  author = {David Eppstein},
  journal = {Networks},
  volume = {35},
  number = {3},
  pages = {173--180},
  year = {2000},
  review = {MR-2001c-90088}}

@article{MR-2001c-90088,
  reviews = {Epp-Nw-00},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Clustering for faster network simplex pivots}},
  volume = {2001c},
  number = {90088},
  year = {2001}}

@article{Epp-JASA-04,
  title = {{Comment on Location-Scale Depth}},
  author = {David Eppstein},
  journal = {J. American Statistical Assoc.},
  volume = {99},
  number = {468},
  pages = {976--979},
  month = {December},
  year = {2004}}

@misc{cs.CG/0009024,
  title = {{Computing the depth of a flat}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0009024},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {2000}}

@inproceedings{BerEpp-SODA-01,
  title = {{Computing the depth of a flat}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0009024},
  booktitle = {Proc. 12th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {700--701},
  month = {January},
  year = {2001}}

@inproceedings{DobEpp-SCG-93,
  title = {{Computing the discrepancy}},
  author = {David P. Dobkin and David Eppstein},
  booktitle = {Proc. 9th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {47--52},
  month = {May},
  year = {1993}}

@article{DobEppMit-ToG-96,
  title = {{Computing the discrepancy with applications to supersampling
    patterns}},
  author = {David P. Dobkin and David Eppstein and Donald P. Mitchell},
  journal = {ACM Trans. Graphics},
  publisher = {ACM},
  volume = {15},
  number = {4},
  pages = {354--376},
  month = {October},
  year = {1996},
  url = {http://doi.acm.org/10.1145/234535.234536}}

@misc{cs.CG/0212046,
  title = {{Confluent drawings: visualizing non-planar diagrams in a planar
    way}},
  author = {Matthew T. Dickerson and David Eppstein and Michael T. Goodrich
    and Jeremy Yu Meng},
  eprint = {cs.CG/0212046},
  howpublished = {ACM Computing Research Repository},
  month = {December},
  year = {2002}}

@inproceedings{DicEppGoo-GD-03,
  title = {{Confluent drawings: visualizing non-planar diagrams in a planar
    way}},
  author = {Matthew T. Dickerson and David Eppstein and Michael T. Goodrich
    and Jeremy Yu Meng},
  eprint = {cs.CG/0212046},
  booktitle = {Proc. 11th Int. Symp. Graph Drawing (GD 2003)},
  number = {2912},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {1--12},
  month = {September},
  year = {2003}}

@inproceedings{EppGooMen-GD-04,
  title = {{Confluent layered drawings}},
  author = {David Eppstein and Michael T. Goodrich and Jeremy Yu Meng},
  eprint = {cs.CG/0507051},
  booktitle = {Proc. 12th Int. Symp. Graph Drawing (GD 2004)},
  number = {3383},
  editor = {J{\'a}nos Pach},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {184--194},
  year = {2004}}

@misc{cs.CG/0507051,
  title = {{Confluent layered drawings}},
  author = {David Eppstein and Michael T. Goodrich and Jeremy Yu Meng},
  eprint = {cs.CG/0507051},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2005}}

@techreport{Epp-TR-92-06,
  title = {{Connectivity, graph minors, and subgraph multiplicity}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-06},
  month = {10 January},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-06.pdf}}

@article{Epp-JGT-93,
  title = {{Connectivity, graph minors, and subgraph multiplicity}},
  author = {David Eppstein},
  journal = {J. Graph Theory},
  volume = {17},
  pages = {409--416},
  year = {1993},
  review = {MR-94i:05075}}

@article{MR-94i:05075,
  reviews = {Epp-JGT-93},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Connectivity, graph minors, and subgraph multiplicity}},
  author = {Gerard Jennhwa Chang},
  number = {94i:05075},
  year = {1994}}

@inproceedings{EppGooMen-GD-05,
  title = {{Delta-confluent drawings}},
  author = {David Eppstein and Michael T. Goodrich and Jeremy Yu Meng},
  booktitle = {Proc. 13th Int. Symp. Graph Drawing (GD 2005)},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  year = {2005},
  note = {To appear.}}

@misc{cs.CG/0307027,
  title = {{Deterministic sampling and range counting in geometric data streams}},
  author = {Amitabha Bagchi and Amitabh Chaudhary and David Eppstein and
    Michael T. Goodrich},
  eprint = {cs.CG/0307027},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2003}}

@inproceedings{BagChaEpp-SCG-04,
  title = {{Deterministic sampling and range counting in geometric data streams}},
  author = {Amitabha Bagchi and Amitabh Chaudhary and David Eppstein and
    Michael T. Goodrich},
  eprint = {cs.CG/0307027},
  booktitle = {Proc. 20th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {144--151},
  year = {2004}}

@misc{math.CO/9907126,
  title = {{Diameter and treewidth in minor-closed graph families}},
  author = {David Eppstein},
  eprint = {math.CO/9907126},
  howpublished = {arXiv.org e-Print archive},
  month = {July},
  year = {1999}}

@article{Epp-Algo-00,
  title = {{Diameter and treewidth in minor-closed graph families}},
  author = {David Eppstein},
  eprint = {math.CO/9907126},
  journal = {Algorithmica},
  volume = {27},
  pages = {275--291},
  year = {2000},
  url = {http://dx.doi.org/10.1007/s004530010020},
  note = {Special issue on treewidth, graph minors, and algorithms},
  review = {MR-2001c-05132}}

@article{MR-2001c-05132,
  reviews = {Epp-Algo-00},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Diameter and treewidth in minor-closed graph families}},
  author = {Xiao Tie Deng},
  volume = {2001c},
  number = {05132},
  year = {2001},
  text = {The main result of this paper is that any minor-closed family has
    the diameter-tree width property if and only if it does not contain all
    apex graphs (graphs that become planar if a vertex, the apex, is removed).
    This property guarantees that every graph in the family with diameter
    no more than $D$ has treewidth no more than $f(D)$, where $f$ is a fixed
    function. Consequently, linear time approximation schemes for several
    optimization problems on these graphs are obtained, as are linear time
    algorithms for subgraph isomorphism and induced subgraph isomorphism.}}

@article{BerCheEpp-AAMS-94,
  title = {{Dihedral bounds for mesh generation in high dimensions}},
  author = {Marshall Wayne Bern and L. Paul Chew and David Eppstein and Jim
    Ruppert},
  journal = {Abstracts of the AMS},
  publisher = {Amer. Math. Soc.},
  volume = {15},
  pages = {366},
  year = {1994},
  note = {From 892nd Meeting Amer. Math. Soc., Brooklyn, April 1994}}

@inproceedings{BerCheEpp-SODA-95,
  title = {{Dihedral bounds for mesh generation in high dimensions}},
  author = {Marshall Wayne Bern and L. Paul Chew and David Eppstein and Jim
    Ruppert},
  booktitle = {Proc. 6th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {189--196},
  month = {January},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerCheEpp-SODA-95.pdf},
  review = {MR-95m:52031}}

@article{MR-95m:52031,
  reviews = {BerCheEpp-SODA-95},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Dihedral bounds for mesh generation in high dimensions}},
  author = {Evangelos Kranakis},
  number = {95m:52031},
  year = {1995}}

@inproceedings{AgaEppMat-FOCS-92,
  title = {{Dynamic algorithms for half-space reporting, proximity problems,
    and geometric minimum spanning trees}},
  author = {Pankaj Kumar Agarwal and David Eppstein and Ji{\v{r}}{\'\i} Matou{\v{s}}ek},
  booktitle = {Proc. 33rd Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {80--89},
  month = {October},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/AgaEppMat-FOCS-92.pdf}}

@techreport{Epp-TR-96-13,
  title = {{Dynamic connectivity in digital images}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {96-13},
  year = {1996},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-13.pdf}}

@article{Epp-IPL-97,
  title = {{Dynamic connectivity in digital images}},
  author = {David Eppstein},
  journal = {Information Processing Letters},
  volume = {62},
  number = {3},
  pages = {121--126},
  month = {May},
  year = {1997}}

@techreport{Epp-TR-92-05,
  title = {{Dynamic Euclidean minimum spanning trees and extrema of binary
    functions}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-05},
  year = {1992}}

@techreport{Epp-TR-92-88,
  title = {{Dynamic Euclidean minimum spanning trees and extrema of binary
    functions}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-88},
  year = {1992}}

@article{Epp-DCG-95,
  title = {{Dynamic Euclidean minimum spanning trees and extrema of binary
    functions}},
  author = {David Eppstein},
  journal = {Discrete {\&} Computational Geometry},
  volume = {13},
  number = {1},
  pages = {111--122},
  month = {January},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-DCG-95.pdf},
  review = {MR-95g:68122}}

@article{MR-95g:68122,
  reviews = {Epp-DCG-95},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Dynamic Euclidean minimum spanning trees and extrema of binary
    functions}},
  number = {95g:68122},
  year = {1995}}

@misc{cs.DS/0207082,
  title = {{Dynamic generators of topologically embedded graphs}},
  author = {David Eppstein},
  eprint = {cs.DS/0207082},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2002}}

@inproceedings{Epp-SODA-03,
  title = {{Dynamic generators of topologically embedded graphs}},
  author = {David Eppstein},
  eprint = {cs.DS/0207082},
  booktitle = {Proc. 14th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {599--608},
  month = {January},
  year = {2003}}

@techreport{EppGalIta-TR-96-056,
  title = {{Dynamic graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano},
  institution = {ALCOM-IT},
  number = {TR-056-96},
  year = {1996}}

@techreport{EppGalIta-TR-96-11,
  title = {{Dynamic graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano},
  address = {via Torino 155, 30173 Venezia Mestre, ITALY},
  institution = {Univ. Ca' Foscari di Venezia, Dip. di Mathematica Applicata
    ed Informatica},
  number = {CS96-11},
  month = {October},
  year = {1996}}

@incollection{EppGalIta-ATCH-99,
  title = {{Dynamic graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano},
  booktitle = {Algorithms and Theory of Computation Handbook},
  publisher = {CRC Press},
  editor = {Mikhail J. Atallah},
  year = {1999},
  url = {http://www.info.uniroma2.it/~italiano/Papers/dyn-survey.ps.Z},
  chapter = {8}}

@techreport{Epp-TR-91-53,
  title = {{Dynamic three-dimensional linear programming}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {91-53},
  year = {1991},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-91-53.pdf}}

@inproceedings{Epp-FOCS-91,
  title = {{Dynamic three-dimensional linear programming}},
  author = {David Eppstein},
  booktitle = {Proc. 32nd Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {488--494},
  month = {October},
  year = {1991}}

@article{Epp-OJC-92,
  title = {{Dynamic three-dimensional linear programming}},
  author = {David Eppstein},
  journal = {ORSA J. Computing},
  volume = {4},
  number = {4},
  pages = {360--368},
  year = {1992},
  month = {Fall},
  note = {Special issue on computational geometry}}

@techreport{BerEdeEpp-TR-92,
  title = {{Edge insertion for optimal triangulation}},
  author = {Marshall Wayne Bern and Herbert Edelsbrunner and David Eppstein
    and Scott A. Mitchell and Tiow-Seng Tan},
  institution = {Univ. of Illinois, Urbana-Champaign, Dept. of Computer Science},
  number = {UILU-ENG-92-1702},
  year = {1992}}

@inproceedings{BerEdeEpp-LATIN-92,
  title = {{Edge insertion for optimal triangulation}},
  author = {Marshall Wayne Bern and Herbert Edelsbrunner and David Eppstein
    and Scott A. Mitchell and Tiow-Seng Tan},
  booktitle = {Proc. 1st Latin American Symp. Theoretical Informatics (LATIN
    1992)},
  number = {583},
  editor = {Imre Simon},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {46--60},
  month = {April},
  year = {1992}}

@article{BerEdeEpp-DCG-93,
  title = {{Edge insertion for optimal triangulation}},
  author = {Marshall Wayne Bern and Herbert Edelsbrunner and David Eppstein
    and Scott A. Mitchell and Tiow-Seng Tan},
  journal = {Discrete {\&} Computational Geometry},
  volume = {10},
  number = {1},
  pages = {47--65},
  year = {1993},
  url = {http://www.iscs.nus.sg/~tants/Paper/eis.ps.gz},
  review = {MR-94i:68279}}

@article{MR-94i:68279,
  reviews = {BerEdeEpp-DCG-93},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Edge insertion for optimal triangulation}},
  author = {Michael S. Martin},
  number = {94i:68279},
  year = {1994}}

@inproceedings{EppGalGia-IAWS-91,
  title = {{Efficient algorithms for sequence analysis}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
    F. Italiano},
  booktitle = {Int. Advanced Worksh. on Sequences, Positano},
  year = {1991},
  url = {http://www.ics.uci.edu/~eppstein/pubs/EppGalGia-IAWS-91.pdf}}

@incollection{EppGalGia-S2-93,
  title = {{Efficient algorithms for sequence analysis}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
    F. Italiano},
  booktitle = {Sequences II: Communication, Security, and Computer Science},
  publisher = {Springer-Verlag},
  editor = {Renato M. Capocelli and De Santis, Alfredo and Ugo Vaccaro},
  pages = {225--244},
  year = {1993},
  note = {From Int. Advanced Worksh. Sequences, Positano, Italy, June 1991}}

@phdthesis{Epp-PhD-89,
  title = {{Efficient algorithms for sequence analysis with concave and convex
    gap costs}},
  author = {David Eppstein},
  address = {New York, NY, 10027, USA},
  school = {Columbia Univ., Computer Science Dept.},
  year = {1989},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-PhD-89.pdf}}

@incollection{EppGalGia-Seq-90,
  title = {{Efficient algorithms with applications to molecular biology}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo},
  booktitle = {Sequences: Combinatorics, Compression, Security, Transmission},
  publisher = {Springer-Verlag},
  editor = {Renato M. Capocelli},
  pages = {59--74},
  year = {1990},
  note = {From Int. Advanced Worksh. Sequences, Positano, Italy, June 1988},
  review = {MR-91a:68125}}

@article{MR-91a:68125,
  reviews = {EppGalGia-Seq-90},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Efficient algorithms with applications to molecular biology}},
  author = {Ralph G. Stanton},
  number = {91a:68125},
  year = {1991}}

@techreport{ChrEppIta-TR-91,
  title = {{Efficient sequential and parallel algorithms for computing recovery
    points in trees and paths}},
  author = {Marek Chrobak and David Eppstein and Giuseppe F. Italiano and
    Moti Yung},
  type = {ALCOM Report},
  institution = {Univ. di Roma ``La Sapienza'', Dip. di Informatica e Sistemistica},
  number = {91-74},
  year = {1991}}

@inproceedings{ChrEppIta-SODA-91,
  title = {{Efficient sequential and parallel algorithms for computing recovery
    points in trees and paths}},
  author = {Marek Chrobak and David Eppstein and Giuseppe F. Italiano and
    Moti Yung},
  booktitle = {Proc. 2nd Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {158--167},
  month = {January},
  year = {1991}}

@misc{cs.CG/9909001,
  title = {{Emerging challenges in computational topology}},
  author = {Marshall Wayne Bern and David Eppstein and others},
  eprint = {cs.CG/9909001},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {1999}}

@article{EppFeiLi-DM-91,
  title = {{Equipartitions of graphs}},
  author = {David Eppstein and Joan Feigenbaum and Chung-Lun Li},
  journal = {Discrete Mathematics},
  volume = {91},
  number = {3},
  pages = {239--248},
  year = {1991},
  url = {http://dx.doi.org/10.1016/0012-365X(90)90233-8},
  review = {MR-92k:05125}}

@article{MR-92k:05125,
  reviews = {EppFeiLi-DM-91},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Equipartitions of graphs}},
  author = {Marek E. Kubale},
  number = {92k:05125},
  year = {1992}}

@misc{cs.DS/0009005,
  title = {{Fast approximation of centrality}},
  author = {David Eppstein and Joseph Yannkae Wang},
  eprint = {cs.DS/0009005},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {2000}}

@inproceedings{EppWan-SODA-01,
  title = {{Fast approximation of centrality}},
  author = {David Eppstein and Joseph Yannkae Wang},
  eprint = {cs.DS/0009005},
  booktitle = {Proc. 12th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {228--229},
  month = {January},
  year = {2001}}

@inproceedings{Epp-SODA-98,
  title = {{Fast hierarchical clustering and other applications of dynamic
    closest pairs}},
  author = {David Eppstein},
  eprint = {cs.DS/9912014},
  booktitle = {Proc. 9th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {619--628},
  month = {January},
  year = {1998},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-SODA-98.pdf}}

@misc{cs.DS/9912014,
  title = {{Fast hierarchical clustering and other applications of dynamic
    closest pairs}},
  author = {David Eppstein},
  eprint = {cs.DS/9912014},
  howpublished = {ACM Computing Research Repository},
  month = {December},
  year = {1999}}

@article{Epp-JEA-00,
  title = {{Fast hierarchical clustering and other applications of dynamic
    closest pairs}},
  author = {David Eppstein},
  eprint = {cs.DS/9912014},
  journal = {J. Experimental Algorithmics},
  publisher = {ACM},
  volume = {5},
  number = {1},
  pages = {1--23},
  month = {June},
  year = {2000},
  url = {http://www.jea.acm.org/2000/EppsteinDynamic/}}

@techreport{AsuDilEpp-TR-92,
  title = {{Fast optimal parallel algorithms for maximal matching in sparse
    graphs}},
  author = {Hari Asuri and Michael B. Dillencourt and David Eppstein and
    George S. Lueker and Mariko Molodowitch},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-01},
  year = {1992}}

@techreport{Epp-TR-94-33,
  title = {{Faster circle packing with application to nonobtuse triangulation}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {94-33},
  year = {1994},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-33.pdf}}

@article{Epp-IJCGA-97,
  title = {{Faster circle packing with application to nonobtuse triangulation}},
  author = {David Eppstein},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {7},
  number = {5},
  pages = {485--491},
  month = {October},
  year = {1997},
  review = {MR-99d:52018}}

@article{MR-99d:52018,
  reviews = {Epp-IJCGA-97},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Faster circle packing with application to nonobtuse triangulation}},
  author = {Frederic Matheus},
  number = {99d:52018},
  year = {1999},
  text = {Numerical computations regarding the discretization of Dirichlet
    problems in polygonal domains need to generate triangulations with right
    or acute angles. The author considers here a recent work of Bern, Mitchell
    and Ruppert which uses circle packings to generate such meshes and speed
    up a key step of their method in which circles are packed into a non-simply
    connected polygonal region to connect its boundary components. 
    
    In the work of Bern et al., this step was computed in $O(n\log\sp {2}n)$
    time. The new method presented here leads to an overall speedup of a
    logarithmic factor, which makes the whole algorithm work in total time
    $O(n\log n)$. 
    
    This method for connecting the boundary components of a polygon relies
    on a combination of several known techniques such as: Voronoi diagrams,
    minimum spanning trees, intersection graphs, neighborhood system algorithms
    of Eppstein, Miller and Teng, and dynamic tree techniques of Sleator
    and Tarjan.}}

@techreport{Epp-TR-96-12,
  title = {{Faster construction of planar two-centers}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {96-12},
  year = {1996},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-12.pdf}}

@inproceedings{Epp-SODA-97,
  title = {{Faster construction of planar two-centers}},
  author = {David Eppstein},
  booktitle = {Proc. 8th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {131--138},
  month = {January},
  year = {1997},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-SODA-97.pdf}}

@techreport{Epp-TR-95-13,
  title = {{Faster geometric $k$-point MST approximation}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-13},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-13.pdf}}

@article{Epp-CGTA-97,
  title = {{Faster geometric $k$-point MST approximation}},
  author = {David Eppstein},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {8},
  pages = {231--240},
  month = {October},
  year = {1997},
  review = {MR-98d:68199}}

@article{MR-98d:68199,
  reviews = {Epp-CGTA-97},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Faster geometric $k$-point MST approximation}},
  number = {98d:68199},
  year = {1998}}

@misc{math.CO/0204007,
  title = {{Fat 4-polytopes and fatter 3-spheres}},
  author = {David Eppstein and Greg Kuperberg and G{\"u}nter M. Ziegler},
  eprint = {math.CO/0204007},
  howpublished = {arXiv.org e-Print archive},
  month = {April},
  year = {2002}}

@incollection{EppKupZie-WK-03,
  title = {{Fat 4-polytopes and fatter 3-spheres}},
  author = {David Eppstein and Greg Kuperberg and G{\"u}nter M. Ziegler},
  eprint = {math.CO/0204007},
  booktitle = {Discrete Geometry: In honor of W. Kuperberg's 60th birthday},
  number = {253},
  editor = {Andras Bezdek},
  series = {Pure and Applied Mathematics},
  publisher = {Marcel Dekker},
  pages = {239--265},
  year = {2003},
  review = {MR-2034720}}

@article{MR-2034720,
  reviews = {EppKupZie-WK-03},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Fat 4-polytopes and fatter 3-spheres}},
  number = {2034720},
  year = {2004}}

@techreport{Epp-TR-95-52,
  title = {{Finding common ancestors and disjoint paths in DAGs}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-52},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-52.pdf}}

@article{EppOveRot-DCG-92,
  title = {{Finding minimum area $k$-gons}},
  author = {David Eppstein and Mark Overmars and G{\"u}nter Rote and Gerhard
    J. Woeginger},
  journal = {Discrete {\&} Computational Geometry},
  volume = {7},
  number = {1},
  pages = {45--58},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/EppOveRot-DCG-92.pdf},
  review = {MR-92k:52026}}

@article{MR-92k:52026,
  reviews = {EppOveRot-DCG-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Finding minimum area $k$-gons}},
  author = {Ivan Stojmenov{\'\i}c},
  number = {92k:52026},
  year = {1992}}

@techreport{Epp-TR-94-26,
  title = {{Finding the $k$ shortest paths}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {94-26},
  year = {1994},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-26.pdf}}

@inproceedings{Epp-FOCS-94,
  title = {{Finding the $k$ shortest paths}},
  author = {David Eppstein},
  booktitle = {Proc. 35th Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {154--165},
  month = {November},
  year = {1994}}

@article{Epp-SJC-98,
  title = {{Finding the $k$ shortest paths}},
  author = {David Eppstein},
  journal = {SIAM J. Computing},
  publisher = {SIAM},
  volume = {28},
  number = {2},
  pages = {652--673},
  year = {1998},
  url = {http://dx.doi.org/10.1137/S0097539795290477},
  review = {MR-99h:05073}}

@article{MR-99h:05073,
  reviews = {Epp-SJC-98},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Finding the $k$ shortest paths}},
  author = {Koduvayur R. Parthasarathy},
  number = {99h:05073},
  year = {1999},
  text = {The $k$-shortest-paths problem is to list the $k$ paths from a
    specified source $s$ to a specified destination $t$ in a digraph, with
    minimum total length. The author considers digraphs admitting self-loops,
    multiple edges and cycles without negative lengths, and the paths are
    not necessarily simple. Using an implicit representation of the paths,
    the author presents, in detail, an algorithm with time complexity $O(m+n\log
    n+k)$ where $n$ and $m$ are the number of vertices and the number of
    edges of the digraph. This also leads to an algorithm of complexity $O(m+n\log
    n+kn)$ for the $k$-shortest-paths problem from a given source $s$ to
    all other vertices of the graph. 
    
    To get the implicit representation, one starts with a single-destination
    $(t)$ shortest path tree $T$ of the given digraph $G$ with source $s$
    and destination $t$ and produces a heap $H\sb G(v)$ at each vertex $v$
    leading to a directed acyclic graph $D(G)$ and through that to a path
    graph $P(G)$, with the property that there is a one-to-one "length-preserving"
    correspondence between $s$-$t$ paths in $G$ and paths starting from the
    root $r$ in $P(G)$ and finally to a 4-heap $H(G)$ whose nodes correspond
    to the $s$-$t$ paths of $G$. After developing a basic algorithm, improvements
    are introduced in the heap construction to attain the above complexity.
    
    
    The improvements in time complexity achieved through this algorithm when
    used for the dynamic programming applications to the following optimization
    problems are discussed at some length: the knapsack problem, sequence
    alignment, inscribed polygons, and genealogical relations. Three open
    problems are suggested.}}

@inproceedings{Epp-SWAT-90,
  title = {{Finding the $k$ smallest spanning trees}},
  author = {David Eppstein},
  booktitle = {Proc. 2nd Scandinavian Worksh. Algorithm Theory (SWAT 1990)},
  number = {447},
  editor = {John Russell Gilbert and Rolf G. Karlsson},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {38--47},
  month = {July},
  year = {1990}}

@article{Epp-BIT-92,
  title = {{Finding the $k$ smallest spanning trees}},
  author = {David Eppstein},
  journal = {BIT},
  volume = {32},
  number = {2},
  pages = {237--248},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-BIT-92.pdf},
  note = {Special issue for 2nd SWAT},
  review = {MR-94e:05082}}

@article{MR-94e:05082,
  reviews = {Epp-BIT-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Finding the $k$ smallest spanning trees}},
  author = {Maciej M. Sys{\l}o},
  number = {94e:05082},
  year = {1994}}

@misc{cs.CG/0108020,
  title = {{Flipping cubical meshes}},
  author = {Marshall Wayne Bern and David Eppstein and Jeffrey Gordon Erickson},
  eprint = {cs.CG/0108020},
  howpublished = {ACM Computing Research Repository},
  month = {August},
  year = {2001}}

@article{BerEppEri-EwC-02,
  title = {{Flipping cubical meshes}},
  author = {Marshall Wayne Bern and David Eppstein and Jeffrey Gordon Erickson},
  eprint = {cs.CG/0108020},
  journal = {Engineering with Computers},
  volume = {18},
  number = {3},
  pages = {173--187},
  month = {October},
  year = {2002}}

@inproceedings{BerEpp-IMR-01,
  title = {{Flipping cubical meshes{}}},
  author = {Marshall Wayne Bern and David Eppstein},
  booktitle = {Proc. 10th Int. Meshing Roundtable},
  publisher = {Sandia Nat. Lab.},
  pages = {19--29},
  month = {October},
  year = {2001}}

@techreport{Epp-TR-95-11,
  title = {{Geometric lower bounds for parametric matroid optimization}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-11},
  year = {1995}}

@inproceedings{Epp-STOC-95,
  title = {{Geometric lower bounds for parametric matroid optimization}},
  author = {David Eppstein},
  booktitle = {Proc. 27th Symp. Theory of Computing},
  publisher = {ACM},
  pages = {662--671},
  month = {June},
  year = {1995},
  url = {http://www.acm.org/pubs/citations/proceedings/stoc/225058/p662-eppstein}}

@article{Epp-DCG-98,
  title = {{Geometric lower bounds for parametric matroid optimization}},
  author = {David Eppstein},
  journal = {Discrete {\&} Computational Geometry},
  volume = {20},
  pages = {463--476},
  year = {1998},
  url = {http://link.springer.de/link/service/journals/00454/bibs/20n4p463.html},
  review = {MR-99h:90082}}

@article{MR-99h:90082,
  reviews = {Epp-DCG-98},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Geometric lower bounds for parametric matroid optimization}},
  author = {De Loera, Jes{\'u}s A.},
  number = {99h:90082},
  year = {1999},
  text = {The author deduces some results on matroid optimization by using
    geometric techniques. For example, the following lower bounds are proved,
    using their relation to polygon arrangements and lower envelopes of line
    segments: (1) There can be $\Omega (nr\sp {1/3})$ different minimum weight
    bases in a matroid with $n$ elements, rank $r$ and element weights linearly
    varying with time. (2) There can be $\Omega (m \alpha(n))$ different
    minimum spanning trees in a graph with $m$ edges, $n$ vertices, and edge
    weights linearly varying with time, where $\alpha(n)$ denotes the inverse
    Ackermann function. 
    
    Recently, T. K. Dey [Discrete Comput. Geom. 19 (1998), no. 3, Special
    Issue, 373--382; MR 98k:52018] obtained an $O(nr\sp {1/3})$ upper bound
    on the number of base changes in a parametric matroid optimization problem,
    that matches the lower bound presented in this article.}}

@inproceedings{DilEppHir-GD-98,
  title = {{Geometric thickness of complete graphs}},
  author = {Michael B. Dillencourt and David Eppstein and Daniel S. Hirschberg},
  eprint = {math.CO/9910185},
  booktitle = {Proc. 6th Int. Symp. Graph Drawing (GD 1998)},
  number = {1547},
  editor = {Sue Whitesides},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {102--110},
  month = {August},
  year = {1998},
  review = {MR-2000g-68118}}

@article{MR-2000g-68118,
  reviews = {DilEppHir-GD-98},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Geometric thickness of complete graphs}},
  volume = {2000g},
  number = {68118},
  year = {2000}}

@misc{math.CO/9910185,
  title = {{Geometric thickness of complete graphs}},
  author = {Michael B. Dillencourt and David Eppstein and Daniel S. Hirschberg},
  eprint = {math.CO/9910185},
  howpublished = {arXiv.org e-Print archive},
  month = {October},
  year = {1999}}

@article{DilEppHir-JGAA-00,
  title = {{Geometric thickness of complete graphs}},
  author = {Michael B. Dillencourt and David Eppstein and Daniel S. Hirschberg},
  eprint = {math.CO/9910185},
  journal = {J. Graph Algorithms {\&} Applications},
  volume = {4},
  number = {3},
  pages = {5--17},
  year = {2000},
  note = {Special issue for Graph Drawing '98},
  review = {MR-2004f:05044}}

@article{MR-2004f:05044,
  reviews = {DilEppHir-JGAA-00},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Geometric thickness of complete graphs}},
  number = {2004f:05044},
  year = {2004}}

@misc{Epp-IMR-01,
  title = {{Global optimization of mesh quality}},
  author = {David Eppstein},
  howpublished = {Tutorial at 10th Int. Meshing Roundtable},
  year = {2001},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-IMR-01.pdf}}

@article{Epp-DCG-03,
  title = {{Guest editor's forward to special issue for ACM Symp. on Computational
    Geometry}},
  author = {David Eppstein},
  journal = {Discrete {\&} Computational Geometry},
  volume = {30},
  number = {1},
  pages = {1--2},
  month = {July},
  year = {2003}}

@article{Epp-JCSS-97,
  title = {{Guest editor's forward to special issue of papers from the 34th
    Annual Symposium on Foundations of Computer Science}},
  author = {David Eppstein},
  journal = {J. Computer {\&} Systems Sciences},
  volume = {54},
  number = {2},
  pages = {263},
  month = {April},
  year = {1997}}

@article{Epp-Algo-98,
  title = {{Guest editor's forword to special issue on dynamic graph algorithms}},
  author = {David Eppstein},
  journal = {Algorithmica},
  volume = {22},
  number = {3},
  pages = {233--234},
  month = {November},
  year = {1998}}

@article{DemDemEpp-CGTA-?,
  title = {{Hinged dissections of polyominoes and polyforms}},
  author = {Erik D. Demaine and Martin L. Demaine and David Eppstein and
    Erich Friedman},
  eprint = {cs.CG/9907018},
  journal = {Computational Geometry Theory {\&} Applications},
  note = {To appear}}

@misc{cs.CG/9907018,
  title = {{Hinged dissections of polyominoes and polyforms}},
  author = {Erik D. Demaine and Martin L. Demaine and David Eppstein and
    Erich Friedman},
  eprint = {cs.CG/9907018},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {1999}}

@inproceedings{DemDemEpp-CCCG-99,
  title = {{Hinged dissections of polyominoes and polyforms}},
  author = {Erik D. Demaine and Martin L. Demaine and David Eppstein and
    Erich Friedman},
  eprint = {cs.CG/9907018},
  booktitle = {Proc. 11th Canad. Conf. Computational Geometry},
  month = {August},
  year = {1999},
  url = {http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp37.pdf}}

@misc{cs.CG/0106032,
  title = {{Hinged kite mirror dissection}},
  author = {David Eppstein},
  eprint = {cs.CG/0106032},
  howpublished = {ACM Computing Research Repository},
  month = {June},
  year = {2001}}

@incollection{BerEppPla-DCG-91,
  title = {{Horizon theorems for lines and polygons}},
  author = {Marshall Wayne Bern and David Eppstein and Paul E. Plassman and
    Frances F. Yao},
  booktitle = {Discrete and Computational Geometry: Papers from the DIMACS
    Special Year},
  number = {6},
  editor = {Jacob E. Goodman and Richard Pollack and William Steiger},
  series = {DIMACS Ser. Discrete Math. and Theoretical Computer Science},
  publisher = {Amer. Math. Soc.},
  pages = {45--66},
  year = {1991},
  review = {MR-92j:52023}}

@article{MR-92j:52023,
  reviews = {BerEppPla-DCG-91},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Horizon theorems for lines and polygons}},
  author = {Robert Connelly},
  number = {92j:52023},
  year = {1992}}

@misc{cs.DS/0009006,
  title = {{Improved algorithms for 3-coloring, 3-edge-coloring, and constraint
    satisfaction}},
  author = {David Eppstein},
  eprint = {cs.DS/0009006},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {2000}}

@inproceedings{Epp-SODA-01,
  title = {{Improved algorithms for 3-coloring, 3-edge-coloring, and constraint
    satisfaction}},
  author = {David Eppstein},
  eprint = {cs.DS/0009006},
  booktitle = {Proc. 12th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {329--337},
  month = {January},
  year = {2001}}

@techreport{Epp-TR-91-60,
  title = {{Improved bounds for intersecting triangles and halving planes}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {91-60},
  year = {1991},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-91-60.pdf}}

@article{Epp-JCT-93,
  title = {{Improved bounds for intersecting triangles and halving planes}},
  author = {David Eppstein},
  journal = {J. Combinatorial Theory, Series A},
  volume = {62},
  pages = {176--182},
  year = {1993},
  review = {MR-94f:52006}}

@article{MR-94f:52006,
  reviews = {Epp-JCT-93},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Improved bounds for intersecting triangles and halving planes}},
  author = {Leroy M. Kelly},
  number = {94f:52006},
  year = {1994}}

@inproceedings{EppGooHir-WADS-05,
  title = {{Improved combinatorial group testing for real-world problem sizes}},
  author = {David Eppstein and Michael T. Goodrich and Daniel S. Hirschberg},
  eprint = {cs.DS/0505048},
  booktitle = {Proc. 9th Worksh. Algorithms and Data Structures (WADS 2005)},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  note = {To appear.}}

@misc{cs.DS/0505048,
  title = {{Improved combinatorial group testing for real-world problem sizes}},
  author = {David Eppstein and Michael T. Goodrich and Daniel S. Hirschberg},
  eprint = {cs.DS/0505048},
  howpublished = {ACM Computing Research Repository},
  month = {May},
  year = {2005}}

@techreport{EppGalIta-TR-93,
  title = {{Improved sparsification}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {93-20},
  year = {1993},
  url = {http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf}}

@misc{cs.CG/9809038,
  title = {{Incremental and decremental maintenance of planar width}},
  author = {David Eppstein},
  eprint = {cs.CG/9809038},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {1998}}

@inproceedings{Epp-SODA-99,
  title = {{Incremental and decremental maintenance of planar width}},
  author = {David Eppstein},
  eprint = {cs.CG/9809038},
  booktitle = {Proc. 10th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {S899--S900},
  month = {January},
  year = {1999}}

@article{Epp-Algs-00,
  title = {{Incremental and decremental maintenance of planar width}},
  author = {David Eppstein},
  eprint = {cs.CG/9809038},
  journal = {J. Algorithms},
  volume = {37},
  number = {2},
  pages = {570--577},
  month = {November},
  year = {2000},
  url = {http://dx.doi.org/10.1006/jagm.2000.1107},
  review = {MR-2001g-68095}}

@article{MR-2001g-68095,
  reviews = {Epp-Algs-00},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Incremental and decremental maintenance of planar width}},
  volume = {2001g},
  number = {68095},
  year = {2001}}

@misc{cs.CG/0010018,
  title = {{Internet packet filter management and rectangle geometry}},
  author = {David Eppstein and Shanmugauelayut Muthukrishnan},
  eprint = {cs.CG/0010018},
  howpublished = {ACM Computing Research Repository},
  month = {October},
  year = {2000}}

@inproceedings{EppMut-SODA-01,
  title = {{Internet packet filter management and rectangle geometry}},
  author = {David Eppstein and Shanmugauelayut Muthukrishnan},
  eprint = {cs.CG/0010018},
  booktitle = {Proc. 12th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {827--835},
  month = {January},
  year = {2001}}

@techreport{EppEri-TR-92-71,
  title = {{Iterated nearest neighbors and finding minimal polytopes}},
  author = {David Eppstein and Jeffrey Gordon Erickson},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-71},
  year = {1992}}

@inproceedings{EppEri-SODA-93,
  title = {{Iterated nearest neighbors and finding minimal polytopes}},
  author = {David Eppstein and Jeffrey Gordon Erickson},
  booktitle = {Proc. 4th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {64--73},
  month = {January},
  year = {1993},
  review = {MR-94c:68197}}

@article{MR-94c:68197,
  reviews = {EppEri-SODA-93},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Iterated nearest neighbors and finding minimal polytopes}},
  number = {94c:68197},
  year = {1994}}

@article{EppEri-DCG-94,
  title = {{Iterated nearest neighbors and finding minimal polytopes}},
  author = {David Eppstein and Jeffrey Gordon Erickson},
  journal = {Discrete {\&} Computational Geometry},
  volume = {11},
  number = {3},
  pages = {321--350},
  month = {April},
  year = {1994},
  url = {http://www.cs.duke.edu/~jeffe/pubs/small.html},
  review = {MR-95a:68100}}

@article{MR-95a:68100,
  reviews = {EppEri-DCG-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Iterated nearest neighbors and finding minimal polytopes}},
  author = {Mark E. Hartmann},
  number = {95a:68100},
  year = {1995}}

@techreport{CarEpp-TR-03,
  title = {{Lazy algorithms for dynamic closest pair with arbitrary distance
    measures}},
  author = {Jean Cardinal and David Eppstein},
  institution = {Univ. Libre de Bruxelles, Computer Science Dept.},
  number = {502},
  year = {2003}}

@inproceedings{CarEpp-ALENEX-04,
  title = {{Lazy algorithms for dynamic closest pair with arbitrary distance
    measures}},
  author = {Jean Cardinal and David Eppstein},
  booktitle = {Joint Proc. Worksh. Algorithm Engineering and Experiments
    (ALENEX) and Worksh. Analytic Algorithmics and Combinatorics (ANALCO)},
  publisher = {ACM and SIAM},
  pages = {112--119},
  year = {2004}}

@techreport{Epp-TR-95-51,
  title = {{Linear complexity hexahedral mesh generation}},
  author = {David Eppstein},
  eprint = {cs.CG/9809109},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-51},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-51.pdf}}

@inproceedings{Epp-SCG-96,
  title = {{Linear complexity hexahedral mesh generation}},
  author = {David Eppstein},
  eprint = {cs.CG/9809109},
  booktitle = {Proc. 12th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {58--67},
  month = {May},
  year = {1996},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-SCG-96.pdf}}

@misc{cs.CG/9809109,
  title = {{Linear complexity hexahedral mesh generation}},
  author = {David Eppstein},
  eprint = {cs.CG/9809109},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {1998}}

@article{Epp-CGTA-99,
  title = {{Linear complexity hexahedral mesh generation}},
  author = {David Eppstein},
  eprint = {cs.CG/9809109},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {12},
  pages = {3--16},
  year = {1999},
  note = {Special issue for 12th Symp. Comp. Geom.},
  review = {MR-2000a:68153}}

@article{MR-2000a:68153,
  reviews = {Epp-CGTA-99},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Linear complexity hexahedral mesh generation}},
  author = {de Figueiredo, Luiz Henrique},
  number = {2000a:68153},
  year = {2000},
  text = {One important problem in mesh generation is how to extend a given
    mesh on the surface of a solid to its interior. Most results on such
    problems, especially theoretical ones, are restricted to the extension
    of triangular meshes to tetrahedral meshes. However, in practice, quadrilateral
    and hexahedral meshes are often preferred because of their numerical
    properties. Few theoretical results are known for this case. For planar
    meshes, it has been proved [S. Ramaswami, P. A. Ramos and G. T. Toussaint,
    Comput. Geom. 9 (1998), no. 4, 257--276; MR 98k:68169] that a polygon
    with $n$ sides can be meshed with convex quadrilaterals if and only if
    $n$ is even. Moreover, $O(n)$ Steiner points suffice as the vertices
    of the internal mesh, and they can be found efficiently. Thurston and
    Mitchell independently proved a similar result for spatial meshes, but
    it is restricted to solids whose boundaries are topological spheres.
    The resulting internal mesh is only topological, not geometric, in the
    sense that the hexahedral elements have curved boundaries and are not
    necessarily convex. Moreover, the size of the internal mesh is not linear
    in the size of the boundary mesh. In this paper, the author removes this
    restriction and proves that any polyhedron which is topologically a sphere
    and whose boundary is composed of an even number of quadrilateral faces
    can be meshed with a linear number of topological cubes. The author has
    made some progress in extending this proof to geometric meshes---only
    a finite number of cases are left to be tested, and this could be done
    by machine---but, as he points out, this extension would not be directly
    practical because the size of the interior mesh may be large, albeit
    linear, and its elements will be poorly shaped.}}

@techreport{EppItaTam-TR-90,
  title = {{Maintenance of a minimum spanning forest in a dynamic planar
    graph}},
  author = {David Eppstein and Giuseppe F. Italiano and Roberto Tamassia
    and Robert E. Tarjan and Jeffery R. Westbrook and Moti Yung},
  address = {35 Olden St., Princeton, NJ, 08544-2087, USA},
  institution = {Princeton Univ., Dept. of Computer Science},
  number = {243-90},
  year = {1990}}

@inproceedings{EppItaTam-SODA-90,
  title = {{Maintenance of a minimum spanning forest in a dynamic planar
    graph}},
  author = {David Eppstein and Giuseppe F. Italiano and Roberto Tamassia
    and Robert E. Tarjan and Jeffery R. Westbrook and Moti Yung},
  booktitle = {Proc. 1st Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {1--11},
  month = {January},
  year = {1990}}

@article{EppItaTam-Algs-92,
  title = {{Maintenance of a minimum spanning forest in a dynamic planar
    graph}},
  author = {David Eppstein and Giuseppe F. Italiano and Roberto Tamassia
    and Robert E. Tarjan and Jeffery R. Westbrook and Moti Yung},
  journal = {J. Algorithms},
  volume = {13},
  number = {1},
  pages = {33--54},
  month = {March},
  year = {1992},
  note = {Special issue for 1st SODA},
  review = {MR-93a:68027}}

@article{MR-93a:68027,
  reviews = {EppItaTam-Algs-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Maintenance of a minimum spanning forest in a dynamic planar
    graph}},
  author = {Mirko K{\v{r}}iv{\'a}nek},
  number = {93a:68027},
  year = {1993}}

@article{EppItaTam-Algs-93,
  title = {{Maintenance of a minimum spanning forest in a dynamic planar
    graph}},
  author = {David Eppstein and Giuseppe F. Italiano and Roberto Tamassia
    and Robert E. Tarjan and Jeffery R. Westbrook and Moti Yung},
  journal = {J. Algorithms},
  volume = {15},
  pages = {173},
  year = {1993},
  note = {Corrigendum},
  review = {MR-94b:68039}}

@article{MR-94b:68039,
  reviews = {EppItaTam-Algs-93},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Maintenance of a minimum spanning forest in a dynamic planar
    graph}},
  number = {94b:68039},
  year = {1994},
  text = {The merge operation defined on page 44 is incompletely defined.
    The merge operation requires that the vertices $u$ and $v$ to be merged
    belong to different trees. Otherwise the merging can produce a cycle.}}

@incollection{BerEpp-CEG-92,
  title = {{Mesh generation and optimal triangulation}},
  author = {Marshall Wayne Bern and David Eppstein},
  booktitle = {Computing in Euclidean Geometry},
  editor = {Ding-Zhu Du and Frank Kwang-Ming Hwang},
  series = {Lecture Notes Series on Computing},
  publisher = {World Scientific},
  pages = {23--90},
  year = {1992},
  number = {1}}

@techreport{BerEpp-TR-92,
  title = {{Mesh generation and optimal triangulation}},
  author = {Marshall Wayne Bern and David Eppstein},
  address = {3333 Coyote Hill Rd., Palo Alto, CA, 94304, USA},
  institution = {Xerox Palo Alto Research Center},
  number = {CSL-92-1},
  year = {1992}}

@incollection{BerEpp-CEG-95,
  title = {{Mesh generation and optimal triangulation}},
  author = {Marshall Wayne Bern and David Eppstein},
  booktitle = {Computing in Euclidean Geometry},
  editor = {Ding-Zhu Du and Frank Kwang-Ming Hwang},
  series = {Lecture Notes Series on Computing},
  publisher = {World Scientific},
  pages = {47--123},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerEpp-CEG-95.pdf},
  number = {4},
  edition = {second}}

@misc{cs.CG/0412025,
  title = {{Minimum dilation stars}},
  author = {David Eppstein and Kevin A. Wortman},
  eprint = {cs.CG/0412025},
  howpublished = {ACM Computing Research Repository},
  month = {December},
  year = {2004}}

@inproceedings{EppWor-SCG-05,
  title = {{Minimum dilation stars}},
  author = {David Eppstein and Kevin A. Wortman},
  eprint = {cs.CG/0412025},
  booktitle = {Proc. 21st Symp. Computational Geometry},
  publisher = {ACM},
  pages = {321--326},
  month = {June},
  year = {2005}}

@techreport{Epp-TR-95-10,
  title = {{Minimum range balanced cuts via dynamic subset sums}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-10},
  year = {1995}}

@article{Epp-Algs-97,
  title = {{Minimum range balanced cuts via dynamic subset sums}},
  author = {David Eppstein},
  journal = {J. Algorithms},
  volume = {23},
  number = {2},
  pages = {375--385},
  month = {May},
  year = {1997},
  url = {http://dx.doi.org/10.1006/jagm.1996.0841},
  review = {MR-98k:05129}}

@article{MR-98k:05129,
  reviews = {Epp-Algs-97},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Minimum range balanced cuts via dynamic subset sums}},
  number = {98k:05129},
  year = {1998}}

@misc{cs.CG/0207081,
  title = {{M{\"o}bius-invariant natural neighbor interpolation}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0207081},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2002}}

@inproceedings{BerEpp-SODA-03,
  title = {{M{\"o}bius-invariant natural neighbor interpolation}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0207081},
  booktitle = {Proc. 14th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {128--129},
  month = {January},
  year = {2003}}

@misc{cs.CG/9912013,
  title = {{Multivariate regression depth}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9912013},
  howpublished = {ACM Computing Research Repository},
  month = {December},
  year = {1999}}

@inproceedings{BerEpp-SCG-00,
  title = {{Multivariate regression depth}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9912013},
  booktitle = {Proc. 16th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {315--321},
  month = {June},
  year = {2000},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerEpp-SCG-00.pdf}}

@article{BerEpp-DCG-02,
  title = {{Multivariate regression depth}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9912013},
  journal = {Discrete {\&} Computational Geometry},
  volume = {28},
  number = {1},
  pages = {1--17},
  month = {July},
  year = {2002},
  review = {MR-2003c:52035}}

@article{MR-2003c:52035,
  reviews = {BerEpp-DCG-02},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Multivariate regression depth}},
  number = {2003c:52035},
  year = {2003}}

@techreport{Epp-TR-91-59,
  title = {{New algorithms for minimum area $k$-gons}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {91-59},
  year = {1991}}

@inproceedings{Epp-SODA-92-kgon,
  title = {{New algorithms for minimum area $k$-gons}},
  author = {David Eppstein},
  booktitle = {Proc. 3rd Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {83--86},
  month = {January},
  year = {1992}}

@techreport{EppEri-TR-92-55,
  title = {{New algorithms for minimum measure simplices and one-dimensional
    weighted Voronoi diagrams}},
  author = {David Eppstein and Jeffrey Gordon Erickson},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-55},
  year = {1992}}

@misc{cs.DS/0507053,
  title = {{Nonrepetitive paths and cycles in graphs with application to
    Sudoku}},
  author = {David Eppstein},
  eprint = {cs.DS/0507053},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2005}}

@inproceedings{Epp-WADS-91,
  title = {{Offline algorithms for dynamic minimum spanning tree problems}},
  author = {David Eppstein},
  booktitle = {Proc. 2nd Worksh. Algorithms and Data Structures (WADS 1991)},
  number = {519},
  editor = {Frank K. H. A. Dehne and J{\"o}rg-Rudiger Sack and Nicola Santoro},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {392--399},
  month = {August},
  year = {1991}}

@techreport{Epp-TR-92-04,
  title = {{Offline algorithms for dynamic minimum spanning tree problems}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-04},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf}}

@article{Epp-Algs-94,
  title = {{Offline algorithms for dynamic minimum spanning tree problems}},
  author = {David Eppstein},
  journal = {J. Algorithms},
  volume = {17},
  number = {2},
  pages = {237--250},
  month = {September},
  year = {1994},
  url = {http://dx.doi.org/10.1006/jagm.1994.1033},
  review = {MR-95e:68168}}

@article{MR-95e:68168,
  reviews = {Epp-Algs-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Offline algorithms for dynamic minimum spanning tree problems}},
  number = {95e:68168},
  year = {1995}}

@article{EppPatYao-DCG-97,
  title = {{On nearest neighbor graphs}},
  author = {David Eppstein and Michael S. Paterson and Frances F. Yao},
  journal = {Discrete {\&} Computational Geometry},
  volume = {17},
  number = {3},
  pages = {263--282},
  month = {April},
  year = {1997},
  url = {http://www.ics.uci.edu/~eppstein/pubs/EppPatYao-DCG-97.pdf},
  review = {MR-98d:05121}}

@article{MR-98d:05121,
  reviews = {EppPatYao-DCG-97},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{On nearest neighbor graphs}},
  author = {Cecil C. Rousseau},
  number = {98d:05121},
  year = {1998}}

@techreport{Epp-TR-89,
  title = {{On reset sequence length}},
  author = {David Eppstein},
  address = {New York, NY, 10027, USA},
  institution = {Columbia Univ., Computer Science Dept.},
  number = {CUCS-440-89},
  year = {1989}}

@article{Epp-SN-87,
  title = {{On the NP-completeness of cryptarithms}},
  author = {David Eppstein},
  journal = {SIGACT News},
  publisher = {ACM},
  volume = {18},
  number = {3},
  pages = {38--40},
  year = {1987},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-SN-87.pdf}}

@article{AroBerEpp-DCG-94,
  title = {{On the number of minimal 1-Steiner trees}},
  author = {Boris Aronov and Marshall Wayne Bern and David Eppstein},
  journal = {Discrete {\&} Computational Geometry},
  volume = {12},
  number = {1},
  pages = {29--34},
  month = {July},
  year = {1994},
  review = {MR-95c:05043}}

@article{MR-95c:05043,
  reviews = {AroBerEpp-DCG-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{On the number of minimal 1-Steiner trees}},
  author = {Ding-Zhu Du},
  number = {95c:05043},
  year = {1995}}

@techreport{Epp-TR-96-14,
  title = {{On the parity of graph spanning tree numbers}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {96-14},
  year = {1996}}

@inproceedings{BarDicEpp-SCG-96,
  title = {{On triangulating three-dimensional polygons}},
  author = {Gill Barequet and Matthew T. Dickerson and David Eppstein},
  booktitle = {Proc. 12th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {38--47},
  month = {May},
  year = {1996},
  url = {ftp://ftp.cs.technion.ac.il/pub/barequet/papers/3dt-socg96.ps.gz}}

@article{BarDicEpp-CGTA-98,
  title = {{On triangulating three-dimensional polygons}},
  author = {Gill Barequet and Matthew T. Dickerson and David Eppstein},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {10},
  number = {3},
  pages = {155--170},
  month = {June},
  year = {1998},
  url = {http://dx.doi.org/10.1016/S0925-7721(98)00005-4},
  review = {MR-99a:68168}}

@article{MR-99a:68168,
  reviews = {BarDicEpp-CGTA-98},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{On triangulating three-dimensional polygons}},
  number = {99a:68168},
  year = {1999}}

@misc{math.CO/0006067,
  title = {{One-dimensional peg solitaire}},
  author = {Cristopher Moore and David Eppstein},
  eprint = {math.CO/0006067},
  howpublished = {arXiv.org e-Print archive},
  month = {June},
  year = {2000}}

@misc{math.CO/0008172,
  title = {{One-dimensional peg solitaire, and duotaire}},
  author = {Cristopher Moore and David Eppstein},
  eprint = {math.CO/0008172},
  howpublished = {arXiv.org e-Print archive}}

@techreport{EppMoo-TR-00,
  title = {{One-dimensional peg solitaire, and duotaire}},
  author = {Cristopher Moore and David Eppstein},
  eprint = {math.CO/0008172},
  type = {working paper},
  address = {1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA},
  organization = {Santa Fe Inst.},
  number = {00-09-050},
  month = {September},
  year = {2000},
  url = {http://www.santafe.edu/sfi/publications/Abstracts/00-09-050abs.html}}

@incollection{MooEpp-MSRI-02,
  title = {{One-dimensional peg solitaire, and duotaire}},
  author = {Cristopher Moore and David Eppstein},
  eprint = {math.CO/0008172},
  booktitle = {More Games of No Chance},
  number = {42},
  editor = {Richard J. Nowakowski},
  series = {MSRI Publications},
  publisher = {Cambridge Univ. Press},
  pages = {341--350},
  year = {2002},
  url = {http://www.msri.org/publications/books/Book42/files/moore.pdf}}

@misc{cs.CG/0101006,
  title = {{Optimal M{\"o}bius transformations for information visualization
    and meshing}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0101006},
  howpublished = {ACM Computing Research Repository},
  month = {January},
  year = {2001}}

@inproceedings{BerEpp-WADS-01-omt,
  title = {{Optimal M{\"o}bius transformations for information visualization
    and meshing}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0101006},
  booktitle = {Proc. 7th Worksh. Algorithms and Data Structures (WADS 2001)},
  number = {2125},
  editor = {Frank K. H. A. Dehne and J{\"o}rg-Rudiger Sack and Roberto Tamassia},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {14--25},
  month = {August},
  year = {2001}}

@inproceedings{AmeBerEpp-SODA-97,
  title = {{Optimal point placement for mesh smoothing}},
  author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9809081},
  booktitle = {Proc. 8th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {528--537},
  month = {January},
  year = {1997},
  url = {http://www.ics.uci.edu/~eppstein/pubs/AmeBerEpp-SODA-97.pdf}}

@misc{cs.CG/9809081,
  title = {{Optimal point placement for mesh smoothing}},
  author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9809081},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {1998}}

@article{AmeBerEpp-Algs-99,
  title = {{Optimal point placement for mesh smoothing}},
  author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9809081},
  journal = {J. Algorithms},
  volume = {30},
  number = {2},
  pages = {302--322},
  month = {February},
  year = {1999},
  url = {http://dx.doi.org/10.1006/jagm.1998.0984},
  note = {Special issue for 8th SODA},
  review = {MR-99m:65028}}

@article{MR-99m:65028,
  reviews = {AmeBerEpp-Algs-99},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Optimal point placement for mesh smoothing}},
  number = {99m:65028},
  year = {1999}}

@misc{cs.CG/0105017,
  title = {{Optimization over zonotopes and training support vector machines}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0105017},
  howpublished = {ACM Computing Research Repository},
  month = {May},
  year = {2001}}

@inproceedings{BerEpp-WADS-01-svm,
  title = {{Optimization over zonotopes and training support vector machines}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0105017},
  booktitle = {Proc. 7th Worksh. Algorithms and Data Structures (WADS 2001)},
  number = {2125},
  editor = {Frank K. H. A. Dehne and J{\"o}rg-Rudiger Sack and Roberto Tamassia},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {111--121},
  month = {August},
  year = {2001}}

@misc{cs.CG/0212007,
  title = {{Optimized color gamuts for tiled displays}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0212007},
  howpublished = {ACM Computing Research Repository},
  month = {December},
  year = {2002}}

@inproceedings{BerEpp-SCG-03,
  title = {{Optimized color gamuts for tiled displays}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/0212007},
  booktitle = {Proc. 19th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {274--281},
  month = {June},
  year = {2003}}

@article{EppGal-AR-88,
  title = {{Parallel algorithmic techniques for combinatorial computation}},
  author = {David Eppstein and Zvi Galil},
  journal = {Annual Reviews in Computer Science},
  publisher = {Annual Reviews},
  volume = {3},
  pages = {233--283},
  year = {1988},
  review = {MR-91g:68042}}

@article{MR-91g:68042,
  reviews = {EppGal-AR-88},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Parallel algorithmic techniques for combinatorial computation}},
  number = {91g:68042},
  year = {1991}}

@techreport{EppGal-TR-88,
  title = {{Parallel algorithmic techniques for combinatorial computation}},
  author = {David Eppstein and Zvi Galil},
  address = {New York, NY, 10027, USA},
  organization = {Columbia Univ., Computer Science Dept.},
  number = {CUCS-326-88},
  year = {1988}}

@inproceedings{EppGal-ICALP-89,
  title = {{Parallel algorithmic techniques for combinatorial computation}},
  author = {David Eppstein and Zvi Galil},
  booktitle = {Proc. 16th Int. Coll. Automata, Languages, and Programming
    (ICALP 1989)},
  number = {372},
  editor = {Giorgio Ausiello and Mariangiola Dezani-Ciancaglini and Della
    Rocca, Simona Ronchi},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {304--318},
  month = {July},
  year = {1989},
  note = {Invited talk by Galil.}}

@inproceedings{BerEppTen-WADS-93,
  title = {{Parallel construction of quadtrees and quality triangulations}},
  author = {Marshall Wayne Bern and David Eppstein and Shang-Hua Teng},
  booktitle = {Proc. 3rd Worksh. Algorithms and Data Structures (WADS 1993)},
  number = {709},
  editor = {Frank K. H. A. Dehne and J{\"o}rg-Rudiger Sack and Nicola Santoro
    and Sue Whitesides},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {188--199},
  month = {August},
  year = {1993},
  review = {MR-94j:68291}}

@article{MR-94j:68291,
  reviews = {BerEppTen-WADS-93},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Parallel construction of quadtrees and quality triangulations}},
  number = {94j:68291},
  year = {1994}}

@techreport{BerEppTen-TR-94,
  title = {{Parallel construction of quadtrees and quality triangulations}},
  author = {Marshall Wayne Bern and David Eppstein and Shang-Hua Teng},
  address = {545 Technology Square, Cambridge, MA, 02139, USA},
  institution = {Massachusetts Inst. Tech., Lab. for Computer Science},
  number = {614},
  year = {1994}}

@article{BerEppTen-IJCGA-99,
  title = {{Parallel construction of quadtrees and quality triangulations}},
  author = {Marshall Wayne Bern and David Eppstein and Shang-Hua Teng},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {9},
  number = {6},
  pages = {517--532},
  month = {December},
  year = {1999}}

@article{Epp-IC-92,
  title = {{Parallel recognition of series parallel graphs}},
  author = {David Eppstein},
  journal = {Information {\&} Computation},
  volume = {98},
  number = {1},
  pages = {41--55},
  month = {May},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-IC-92.pdf},
  review = {MR-92m:05180}}

@article{MR-92m:05180,
  reviews = {Epp-IC-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Parallel recognition of series parallel graphs}},
  number = {92m:05180},
  year = {1992}}

@inproceedings{AgaEppGui-FOCS-98,
  title = {{Parametric and kinetic minimum spanning trees}},
  author = {Pankaj Kumar Agarwal and David Eppstein and Leonidas J. Guibas
    and Monika Rauch Henzinger},
  booktitle = {Proc. 39th Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {596--605},
  month = {November},
  year = {1998},
  url = {http://www.ics.uci.edu/~eppstein/pubs/AgaEppGui-FOCS-98.pdf}}

@techreport{Epp-TR-91-54,
  title = {{Persistence, offline algorithms, and space compaction}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {91-54},
  year = {1991},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-91-54.pdf}}

@misc{cs.CC/0008025,
  title = {{Phutball endgames are hard}},
  author = {Erik D. Demaine and Martin L. Demaine and David Eppstein},
  eprint = {cs.CC/0008025},
  howpublished = {ACM Computing Research Repository},
  month = {August},
  year = {2000}}

@incollection{DemDemEpp-MSRI-02,
  title = {{Phutball endgames are hard}},
  author = {Erik D. Demaine and Martin L. Demaine and David Eppstein},
  eprint = {cs.CC/0008025},
  booktitle = {More Games of No Chance},
  number = {42},
  editor = {Richard J. Nowakowski},
  series = {MSRI Publications},
  publisher = {Cambridge Univ. Press},
  pages = {351--360},
  year = {2002},
  url = {http://www.msri.org/publications/books/Book42/files/dephut.pdf},
  review = {MR-2004b:91042}}

@article{MR-2004b:91042,
  reviews = {DemDemEpp-MSRI-02},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Phutball endgames are hard}},
  number = {2004b:91042},
  year = {2004}}

@article{ChrEpp-TCS-91,
  title = {{Planar orientations with low out-degree and compaction of adjacency
    matrices}},
  author = {Marek Chrobak and David Eppstein},
  journal = {Theoretical Computer Science},
  volume = {86},
  number = {2},
  pages = {243--266},
  month = {September},
  year = {1991},
  url = {http://www.ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf},
  review = {MR-93a:68114}}

@article{MR-93a:68114,
  reviews = {ChrEpp-TCS-91},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Planar orientations with low out-degree and compaction of adjacency
    matrices}},
  author = {G. P. Bhattacharjee},
  number = {93a:68114},
  year = {1993}}

@inproceedings{BerEpp-SCG-91,
  title = {{Polynomial-size non-obtuse triangulation of polygons}},
  author = {Marshall Wayne Bern and David Eppstein},
  booktitle = {Proc. 7th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {342--350},
  month = {June},
  year = {1991}}

@article{BerEpp-IJCGA-92,
  title = {{Polynomial-size non-obtuse triangulation of polygons}},
  author = {Marshall Wayne Bern and David Eppstein},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {2},
  number = {3},
  pages = {241--255},
  month = {September},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerEpp-IJCGA-92.pdf},
  note = {Special issue for 7th SCG},
  review = {MR-94e:52016a}}

@article{MR-94e:52016a,
  reviews = {BerEpp-IJCGA-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Polynomial-size non-obtuse triangulation of polygons}},
  author = {Nikolai M. Korneenko},
  number = {94e:52016a},
  year = {1994}}

@article{BerEpp-IJCGA-92-err,
  title = {{Polynomial-size non-obtuse triangulation of polygons}},
  author = {Marshall Wayne Bern and David Eppstein},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {2},
  number = {4},
  pages = {449--450},
  month = {December},
  year = {1992},
  note = {Errata correcting printers' errors in original journal publication},
  review = {MR-94e:52016b}}

@article{MR-94e:52016b,
  reviews = {BerEpp-IJCGA-92-err},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Polynomial-size non-obtuse triangulation of polygons}},
  author = {Nikolai M. Korneenko},
  number = {94e:52016b},
  year = {1994}}

@article{ItaEpp-JC-99,
  title = {{Preface to Festschrift for Zvi Galil}},
  author = {Giuseppe F. Italiano and David Eppstein},
  journal = {J. Complexity},
  volume = {15},
  number = {1},
  pages = {1--3},
  month = {March},
  year = {1999}}

@inproceedings{EppHemTis-ICCI-89,
  title = {{Probabilistic and unambiguous computation are incomparable}},
  author = {David Eppstein and Lane A. Hemachandra and James Tisdall and
    B{\"u}lent Yener},
  booktitle = {Proc. 1st Int. Conf. Computing {\&} Information},
  pages = {65--70},
  year = {1989}}

@techreport{EppHemTis-TR-90,
  title = {{Probabilistic and unambiguous computation are incomparable}},
  author = {David Eppstein and Lane A. Hemachandra and James Tisdall and
    B{\"u}lent Yener},
  institution = {Univ. of Rochester, Dept. of Computer Science},
  number = {335},
  year = {1990}}

@inproceedings{BerEppGil-FOCS-90,
  title = {{Provably good mesh generation}},
  author = {Marshall Wayne Bern and David Eppstein and John Russell Gilbert},
  booktitle = {Proc. 31st Symp. Foundations of Computer Science},
  publisher = {IEEE},
  volume = {I},
  pages = {231--241},
  month = {October},
  year = {1990},
  review = {MR-92k:65132}}

@article{MR-92k:65132,
  reviews = {BerEppGil-FOCS-90},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Provably good mesh generation}},
  number = {92k:65132},
  year = {1992}}

@article{BerEppGil-JCSS-94,
  title = {{Provably good mesh generation}},
  author = {Marshall Wayne Bern and David Eppstein and John Russell Gilbert},
  journal = {J. Computer {\&} Systems Sciences},
  volume = {48},
  number = {3},
  pages = {384--409},
  month = {June},
  year = {1994},
  note = {Special issue for 31st FOCS},
  review = {MR-95c:65235}}

@article{MR-95c:65235,
  reviews = {BerEppGil-JCSS-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Provably good mesh generation}},
  number = {95c:65235},
  year = {1995}}

@inproceedings{BerEpp-CGC-97,
  title = {{Quadrilateral meshing by circle packing}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9908016},
  booktitle = {Proc. 2nd CGC Worksh. Computational Geometry},
  year = {1997}}

@inproceedings{BerEpp-IMR-97,
  title = {{Quadrilateral meshing by circle packing}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9908016},
  booktitle = {Proc. 6th Int. Meshing Roundtable},
  publisher = {Sandia Nat. Lab.},
  pages = {7--20},
  month = {October},
  year = {1997},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerEpp-MRT-97.pdf}}

@misc{cs.CG/9908016,
  title = {{Quadrilateral meshing by circle packing}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9908016},
  howpublished = {ACM Computing Research Repository},
  month = {August},
  year = {1999}}

@article{BerEpp-IJCGA-00,
  title = {{Quadrilateral meshing by circle packing}},
  author = {Marshall Wayne Bern and David Eppstein},
  eprint = {cs.CG/9908016},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {10},
  number = {4},
  pages = {347--360},
  month = {August},
  year = {2000},
  review = {MR-2001f-52031}}

@article{MR-2001f-52031,
  reviews = {BerEpp-IJCGA-00},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Quadrilateral meshing by circle packing}},
  volume = {2001f},
  number = {52031},
  year = {2001}}

@misc{cs.DS/0304018,
  title = {{Quasiconvex analysis of backtracking algorithms}},
  author = {David Eppstein},
  eprint = {cs.DS/0304018},
  howpublished = {ACM Computing Research Repository},
  month = {April},
  year = {2003}}

@inproceedings{Epp-SODA-04-qaba,
  title = {{Quasiconvex analysis of backtracking algorithms}},
  author = {David Eppstein},
  eprint = {cs.DS/0304018},
  booktitle = {Proc. 15th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {781--790},
  month = {January},
  year = {2004}}

@incollection{Epp-MSRI-05,
  title = {{Quasiconvex programming}},
  author = {David Eppstein},
  eprint = {cs.CG/0412046},
  booktitle = {Combinatorial and Computational Geometry},
  editor = {Jacob E. Goodman and J{\'a}nos Pach and Emo Welzl},
  series = {MSRI Publications},
  publisher = {Cambridge Univ. Press},
  note = {To appear.}}

@misc{cs.CG/0412046,
  title = {{Quasiconvex programming}},
  author = {David Eppstein},
  eprint = {cs.CG/0412046},
  howpublished = {ACM Computing Research Repository},
  month = {December},
  year = {2004}}

@inproceedings{EppEri-SCG-98,
  title = {{Raising roofs, crashing cycles, and playing pool: applications
    of a data structure for finding pairwise interactions}},
  author = {David Eppstein and Jeffrey Gordon Erickson},
  booktitle = {Proc. 14th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {58--67},
  month = {June},
  year = {1998},
  review = {MR-2000i-68185}}

@article{MR-2000i-68185,
  reviews = {EppEri-SCG-98},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Raising roofs, crashing cycles, and playing pool: applications
    of a data structure for finding pairwise interactions}},
  volume = {2000i},
  number = {68185},
  year = {2000}}

@article{EppEri-DCG-99,
  title = {{Raising roofs, crashing cycles, and playing pool: applications
    of a data structure for finding pairwise interactions}},
  author = {David Eppstein and Jeffrey Gordon Erickson},
  journal = {Discrete {\&} Computational Geometry},
  volume = {22},
  number = {4},
  pages = {569--592},
  year = {1999},
  note = {Special issue for SCG 1998}}

@misc{Epp-smr-04,
  title = {{Re: Geometry problem: Optimal direction. Known results?}},
  author = {David Eppstein},
  howpublished = {Message to sci.math.research bulletin board},
  month = {21 May},
  year = {2004},
  url = {http://mathforum.org/epigone/sci.math.research/slexyaxsle}}

@inproceedings{EppGiv-ESCODES-02,
  title = {{Reference caching using unit distance redundant codes for activity
    reduction on address buses}},
  author = {David Eppstein and Tony Digaleh Givargis},
  booktitle = {Proc. Worksh. Embedded System Codesign (ESCODES '02)},
  pages = {43--48},
  month = {September},
  year = {2002}}

@misc{cs.CG/9809037,
  title = {{Regression depth and center points}},
  author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein
    and Shang-Hua Teng},
  eprint = {cs.CG/9809037},
  howpublished = {ACM Computing Research Repository},
  month = {September},
  year = {1998}}

@inproceedings{AmeBerEpp-CGC-98,
  title = {{Regression depth and center points}},
  author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein
    and Shang-Hua Teng},
  eprint = {cs.CG/9809037},
  booktitle = {Proc. 3rd CGC Worksh. Computational Geometry},
  month = {October},
  year = {1998},
  url = {http://www.cs.brown.edu/cgc/cgc98/final/final9.pdf}}

@article{AmeBerEpp-DCG-00,
  title = {{Regression depth and center points}},
  author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein
    and Shang-Hua Teng},
  eprint = {cs.CG/9809037},
  journal = {Discrete {\&} Computational Geometry},
  volume = {23},
  number = {3},
  pages = {305--323},
  year = {2000},
  url = {http://link.springer-ny.com/link/service/journals/00454/bibs/0023003/00230305.html},
  review = {MR-2001e-52024}}

@article{MR-2001e-52024,
  reviews = {AmeBerEpp-DCG-00},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Regression depth and center points}},
  author = {P. Laurie Davies},
  volume = {2001e},
  number = {52024},
  year = {2001},
  text = {P. J. Rousseeuw and M. Hubert [Discrete Comput. Geom. 22 (1999),
    no. 2, 167--176; MR 2000e:52024; J. Amer. Statist. Assoc. 94 (1999),
    no. 446, 388--433; MR 2000i:62070] made the following two conjectures
    concerning the regression depth of points in $d$-dimensional Euclidean
    space: Conjecture 1. For any $d$-dimensional set of $n$ points there
    exists a hyperplane having regression depth $\lceil\frac{n}{d+1}\rceil$.
    Conjecture 2. For any point set there exist a partition into $\lceil
    \frac{n}{d+1}\rceil$ subsets and a hyperplane that has nonzero regression
    depth in each subset. The authors prove the first conjecture and make
    some progress on the second. The problems arise in the context of robust
    regression and have a natural geometric formulation. The proofs are based
    on projective geometry and are consequently of a completely different
    nature from the usual proofs of theorems in the area of robust statistics.
    The authors also consider the computational aspects of the problems.}}

@techreport{Epp-TR-95-50,
  title = {{Representing all minimum spanning trees with applications to
    counting and generation}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-50},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-50.pdf}}

@inproceedings{Epp-ICALP-88,
  title = {{Reset sequences for monotonic automata}},
  author = {David Eppstein},
  booktitle = {Proc. 15th Int. Coll. Automata, Languages, and Programming
    (ICALP 1988)},
  number = {317},
  editor = {Timo Lepist{\"o} and Arto Salomaa},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {230--238},
  month = {July},
  year = {1988}}

@article{Epp-SJC-90,
  title = {{Reset sequences for monotonic automata}},
  author = {David Eppstein},
  journal = {SIAM J. Computing},
  publisher = {SIAM},
  volume = {19},
  number = {3},
  pages = {500--510},
  month = {June},
  year = {1990},
  review = {MR-91f:68070}}

@article{MR-91f:68070,
  reviews = {Epp-SJC-90},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Reset sequences for monotonic automata}},
  author = {K. Vairavan},
  number = {91f:68070},
  year = {1991}}

@misc{cs.AI/0004003,
  title = {{Searching for spaceships}},
  author = {David Eppstein},
  eprint = {cs.AI/0004003},
  howpublished = {ACM Computing Research Repository},
  month = {April},
  year = {2000}}

@incollection{Epp-MSRI-02,
  title = {{Searching for spaceships}},
  author = {David Eppstein},
  eprint = {cs.AI/0004003},
  booktitle = {More Games of No Chance},
  number = {42},
  editor = {Richard J. Nowakowski},
  series = {MSRI Publications},
  publisher = {Cambridge Univ. Press},
  pages = {433--453},
  year = {2002},
  url = {http://www.msri.org/publications/books/Book42/files/eppstein.pdf},
  review = {MR-2004b:91044}}

@article{MR-2004b:91044,
  reviews = {Epp-MSRI-02},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Searching for spaceships}},
  number = {2004b:91044},
  year = {2004}}

@inproceedings{BraEppGoo-GD-03,
  title = {{Selected open problems in graph drawing}},
  author = {Franz-Josef Brandenburg and David Eppstein and Michael T. Goodrich
    and Stephen G. Kobourov and Giuseppe Liotta and Petra Mutzel},
  booktitle = {Proc. 11th Int. Symp. Graph Drawing (GD 2003)},
  number = {2912},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {515--539},
  month = {September},
  year = {2003}}

@misc{math.CO/0109195,
  title = {{Separating geometric thickness from book thickness}},
  author = {David Eppstein},
  eprint = {math.CO/0109195},
  howpublished = {arXiv.org e-Print archive},
  month = {September},
  year = {2001}}

@inproceedings{Epp-GD-02,
  title = {{Separating thickness from geometric thickness}},
  author = {David Eppstein},
  eprint = {math.CO/0204252},
  booktitle = {Proc. 10th Int. Symp. Graph Drawing (GD 2002)},
  number = {2528},
  editor = {Michael T. Goodrich and Stephen G. Kobourov},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {150--161},
  year = {2002}}

@misc{math.CO/0204252,
  title = {{Separating thickness from geometric thickness}},
  author = {David Eppstein},
  eprint = {math.CO/0204252},
  howpublished = {arXiv.org e-Print archive},
  month = {April},
  year = {2002}}

@incollection{Epp-TTGG-04,
  title = {{Separating thickness from geometric thickness}},
  author = {David Eppstein},
  eprint = {math.CO/0204252},
  booktitle = {Towards a Theory of Geometric Graphs},
  number = {342},
  editor = {J{\'a}nos Pach},
  series = {Contemporary Mathematics},
  publisher = {Amer. Math. Soc.},
  pages = {75--86},
  year = {2004}}

@inproceedings{EppGalIta-STOC-93,
  title = {{Separator based sparsification for dynamic planar graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
    H. Spencer},
  booktitle = {Proc. 25th Symp. Theory of Computing},
  publisher = {ACM},
  pages = {208--217},
  month = {May},
  year = {1993},
  url = {http://www.acm.org/pubs/citations/proceedings/stoc/167088/p208-eppstein/}}

@article{EppGalIta-JCSS-96,
  title = {{Separator based sparsification I: planarity testing and minimum
    spanning trees}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
    H. Spencer},
  journal = {J. Computer {\&} Systems Sciences},
  volume = {52},
  number = {1},
  pages = {3--27},
  month = {February},
  year = {1996},
  url = {http://dx.doi.org/10.1006/jcss.1996.0002},
  note = {Special issue for 25th STOC},
  review = {MR-97c:05052}}

@article{MR-97c:05052,
  reviews = {EppGalIta-JCSS-96},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Separator based sparsification I: planarity testing and minimum
    spanning trees}},
  author = {Fabrizio Luccio},
  number = {97c:05052},
  year = {1997},
  text = {Based on the fundamental sparsification technique devised by Eppstein,
    Galil, Italiano and Nissenzweig for the design of dynamic graph algorithms,
    this paper shows how a planar graph can be efficiently processed under
    the insertions and deletions of edges that preserve planarity. Although
    the definition of planarity crucially relies on the concept of plane
    embedding, the present technique is applied independently of the embedding,
    which may be altered by the graph changes.
    
    The major results are a fully dynamic planarity test working in $O(n^{1/2})$
    amortized time per update or query, where $n$ is the number of vertices,
    and various efficient dynamic algorithms to maintain connected components,
    minimum spanning forests, and 2-edge-connected components, all valid
    for planar graphs. As an overall comment, this is a significant and useful
    addition to the algorithmic theory of planar graphs.}}

@techreport{EppGalIta-TR-96-13,
  title = {{Separator based sparsification II: edge and vertex connectivity}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
    H. Spencer},
  address = {via Torino 155, 30173 Venezia Mestre, ITALY},
  institution = {Univ. Ca' Foscari di Venezia, Dip. di Mathematica Applicata
    ed Informatica},
  pages = {CS96-13},
  month = {October},
  year = {1996}}

@article{EppGalIta-SJC-99,
  title = {{Separator based sparsification II: edge and vertex connectivity}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas
    H. Spencer},
  journal = {SIAM J. Computing},
  publisher = {SIAM},
  volume = {28},
  number = {1},
  pages = {341--381},
  year = {1999},
  url = {http://dx.doi.org/10.1137/S0097539794269072},
  review = {MR-99g:05058}}

@article{MR-99g:05058,
  reviews = {EppGalIta-SJC-99},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Separator based sparsification II: edge and vertex connectivity}},
  author = {Fabrizio Luccio},
  number = {99g:05058},
  year = {1999},
  text = {A continuation of a series of basic contributions on dynamic graphs,
    produced by the same authors [see Part I, J. Comput. System Sci. 52 (1996),
    no. 1, 3--27; MR 97c:05052], this paper deals with the maintenance of
    a planar graph under insertion and deletion of edges. The main results
    are low-complexity amortized algorithms to retain information about vertex
    connectivity. Although the definition of planarity relies on the existence
    of a plane embedding, the authors devise techniques to keep the graph
    planar under edge insertion without reference to any embedding (which
    may in fact change). 
    
    This is another significant contribution to the important field of plane
    graph algorithms, based on the concept of sparse certificate.}}

@techreport{Epp-TR-88,
  title = {{Sequence comparison with mixed convex and concave costs}},
  author = {David Eppstein},
  address = {New York, NY, 10027, USA},
  institution = {Columbia Univ., Computer Science Dept.},
  number = {CUCS-382-88},
  year = {1988}}

@article{Epp-Algs-90,
  title = {{Sequence comparison with mixed convex and concave costs}},
  author = {David Eppstein},
  journal = {J. Algorithms},
  volume = {11},
  number = {1},
  pages = {85--101},
  month = {March},
  year = {1990},
  review = {MR-91h:68031}}

@article{MR-91h:68031,
  reviews = {Epp-Algs-90},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Sequence comparison with mixed convex and concave costs}},
  number = {91h:68031},
  year = {1991}}

@techreport{Epp-TR-92-86,
  title = {{Sets of points with many halving lines}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-86},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-86.pdf}}

@misc{cs.DS/9907001,
  title = {{Setting parameters by example}},
  author = {David Eppstein},
  eprint = {cs.DS/9907001},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {1999}}

@inproceedings{Epp-FOCS-99,
  title = {{Setting parameters by example}},
  author = {David Eppstein},
  eprint = {cs.DS/9907001},
  booktitle = {Proc. 40th Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {309--318},
  month = {October},
  year = {1999}}

@article{Epp-SJC-03,
  title = {{Setting parameters by example}},
  author = {David Eppstein},
  eprint = {cs.DS/9907001},
  journal = {SIAM J. Computing},
  publisher = {SIAM},
  volume = {32},
  number = {3},
  pages = {643--653},
  year = {2003},
  url = {http://dx.doi.org/10.1137/S0097539700370084},
  review = {MR-2004g:90114}}

@article{MR-2004g:90114,
  reviews = {Epp-SJC-03},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Setting parameters by example}},
  author = {Sheng Bau},
  number = {2004g:90114},
  year = {2004},
  text = {If a parametric optimization problem and a desired optimal solution
    are given, the parameter values that lead to the given problem and the
    solution are to be sought. This is an "inverse parametric optimization"
    problem. This paper describes algorithms for solving such problems for
    minimum spanning trees, shortest paths and some other subgraph problems
    and discusses applications in multicast routing, vehicle path planning,
    resource allocation, and board game programming.}}

@misc{Epp-ct-99,
  title = {{Shortest path along an MST}},
  author = {David Eppstein},
  howpublished = {Message to comp.theory bulletin board},
  month = {April},
  year = {1999},
  url = {http://groups.google.com/groups?threadm=14098.38770.666234.83882@euclid.ics.uci.edu}}

@inproceedings{EppHar-SODA-99,
  title = {{Shortest paths in an arrangement with $k$ line orientations}},
  author = {David Eppstein and David Hart},
  booktitle = {Proc. 10th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {310--316},
  month = {January},
  year = {1999}}

@article{EppHemTis-MST-92,
  title = {{Simultaneous strong separations of probabilistic and unambiguous
    complexity classes}},
  author = {David Eppstein and Lane A. Hemachandra and James Tisdall and
    B{\"u}lent Yener},
  journal = {Mathematical Systems Theory},
  volume = {25},
  number = {1},
  pages = {23--36},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/EppHemTis-MST-92.pdf},
  review = {MR-92j:68031}}

@article{MR-92j:68031,
  reviews = {EppHemTis-MST-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Simultaneous strong separations of probabilistic and unambiguous
    complexity classes}},
  author = {Marius Zimand},
  number = {92j:68031},
  year = {1992}}

@inproceedings{GopEpp-EG-04,
  title = {{Single-strip triangulation of manifolds with arbitrary topology}},
  author = {Gopi Meenakshisundaram and David Eppstein},
  eprint = {cs.CG/0405036},
  booktitle = {Proc. 25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics
    '04)},
  pages = {371--379},
  year = {2004},
  note = {{\it Computer Graphics Forum}, vol. 23, no. 3.
    Winner, second-best paper award.}}

@inproceedings{GopEpp-SCG-04,
  title = {{Single-strip triangulation of manifolds with arbitrary topology}},
  author = {Gopi Meenakshisundaram and David Eppstein},
  eprint = {cs.CG/0405036},
  booktitle = {Proc. 20th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {455--456},
  year = {2004},
  note = {Abstract for video in 13th Video Review of Computational Geometry.}}

@misc{cs.CG/0405036,
  title = {{Single-strip triangulation of manifolds with arbitrary topology}},
  author = {Gopi Meenakshisundaram and David Eppstein},
  eprint = {cs.CG/0405036},
  howpublished = {ACM Computing Research Repository},
  month = {May},
  year = {2004}}

@inproceedings{ArgEppGoo-PODC-05,
  title = {{Skip-webs: efficient distributed data structures for multi-dimensional
    data sets}},
  author = {Lars Arge and David Eppstein and Michael T. Goodrich},
  eprint = {cs.DC/0507050},
  booktitle = {Proc. 24th ACM SIGACT-SIGOPS Symp. Principles of Distributed
    Computing (PODC 2005)},
  note = {To appear.}}

@misc{cs.DC/0507050,
  title = {{Skip-webs: efficient distributed data structures for multi-dimensional
    data sets}},
  author = {Lars Arge and David Eppstein and Michael T. Goodrich},
  eprint = {cs.DC/0507050},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2005}}

@misc{cs.DS/0011009,
  title = {{Small maximal independent sets and faster exact graph coloring}},
  author = {David Eppstein},
  eprint = {cs.DS/0011009},
  howpublished = {ACM Computing Research Repository},
  month = {November},
  year = {2000}}

@inproceedings{Epp-WADS-01,
  title = {{Small maximal independent sets and faster exact graph coloring}},
  author = {David Eppstein},
  eprint = {cs.DS/0011009},
  booktitle = {Proc. 7th Worksh. Algorithms and Data Structures (WADS 2001)},
  number = {2125},
  editor = {Frank K. H. A. Dehne and J{\"o}rg-Rudiger Sack and Roberto Tamassia},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {462--470},
  month = {August},
  year = {2001},
  review = {MR-2003j:05117}}

@article{MR-2003j:05117,
  reviews = {Epp-WADS-01},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Small maximal independent sets and faster exact graph coloring}},
  number = {2003j:05117},
  year = {2003}}

@article{Epp-JGAA-03,
  title = {{Small maximal independent sets and faster exact graph coloring}},
  author = {David Eppstein},
  eprint = {cs.DS/0011009},
  journal = {J. Graph Algorithms {\&} Applications},
  volume = {7},
  number = {2},
  pages = {131--140},
  year = {2003},
  note = {Special issue for WADS'01}}

@techreport{Epp-TR-96-16,
  title = {{Spanning trees and spanners}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {96-16},
  year = {1996},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf}}

@incollection{Epp-HCG-00,
  title = {{Spanning trees and spanners}},
  author = {David Eppstein},
  booktitle = {Handbook of Computational Geometry},
  publisher = {Elsevier},
  editor = {J{\"o}rg-Rudiger Sack and Jorge Urrutia},
  pages = {425--461},
  year = {2000},
  chapter = {9}}

@inproceedings{EppGalGia-SODA-90,
  title = {{Sparse dynamic programming}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
    F. Italiano},
  booktitle = {Proc. 1st Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {513--522},
  month = {January},
  year = {1990}}

@techreport{EppGalIta-TR-89-I,
  title = {{Sparse dynamic programming I: linear cost functions}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
    F. Italiano},
  address = {New York, NY, 10027, USA},
  institution = {Columbia Univ., Computer Science Dept.},
  number = {CUCS-471-89},
  year = {1989}}

@article{EppGalGia-JACM-92-I,
  title = {{Sparse dynamic programming I: linear cost functions}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
    F. Italiano},
  journal = {J. ACM},
  publisher = {ACM},
  volume = {39},
  number = {3},
  pages = {519--545},
  month = {July},
  year = {1992},
  url = {http://www.acm.org/pubs/citations/journals/jacm/1992-39-3/p519-eppstein/},
  review = {MR-93i:90107a}}

@article{MR-93i:90107a,
  reviews = {EppGalGia-JACM-92-I},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Sparse dynamic programming I: linear cost functions}},
  author = {Moshe Sniedovich},
  number = {93i:90107a},
  year = {1993}}

@techreport{EppGalIta-TR-89-II,
  title = {{Sparse dynamic programming II: convex and concave cost functions}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
    F. Italiano},
  address = {New York, NY, 10027, USA},
  institution = {Columbia Univ., Computer Science Dept.},
  number = {CUCS-472-89},
  year = {1989}}

@article{EppGalGia-JACM-92-II,
  title = {{Sparse dynamic programming II: convex and concave cost functions}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo and Giuseppe
    F. Italiano},
  journal = {J. ACM},
  publisher = {ACM},
  volume = {39},
  number = {3},
  pages = {546--567},
  month = {July},
  year = {1992},
  url = {http://www.acm.org/pubs/citations/journals/jacm/1992-39-3/p546-eppstein/},
  review = {MR-93i:90107b}}

@article{MR-93i:90107b,
  reviews = {EppGalGia-JACM-92-II},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Sparse dynamic programming II: convex and concave cost functions}},
  author = {Moshe Sniedovich},
  number = {93i:90107b},
  year = {1993}}

@inproceedings{EppGalIta-FOCS-92,
  title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
    Nissenzweig},
  booktitle = {Proc. 33rd Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {60--69},
  month = {October},
  year = {1992}}

@techreport{EppGalIta-IBM-93,
  title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
    Nissenzweig},
  address = {Rt. 134, Box 218, Yorktown Heights, NY, 10598, USA},
  institution = {IBM, T. J. Watson Research Ctr.},
  number = {RC 19272 (83907)},
  year = {1993}}

@techreport{EppGalIta-TR-96-10,
  title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
    Nissenzweig},
  address = {via Torino 155, 30173 Venezia Mestre, ITALY},
  institution = {Univ. Ca' Foscari di Venezia, Dip. di Mathematica Applicata
    ed Informatica},
  number = {CS96-10},
  month = {October},
  year = {1996}}

@article{EppGalIta-JACM-97,
  title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
  author = {David Eppstein and Zvi Galil and Giuseppe F. Italiano and Amnon
    Nissenzweig},
  journal = {J. ACM},
  publisher = {ACM},
  volume = {44},
  number = {5},
  pages = {669--696},
  month = {September},
  year = {1997},
  url = {http://doi.acm.org/10.1145/265910.265914},
  review = {MR-98k:68039}}

@article{MR-98k:68039,
  reviews = {EppGalIta-JACM-97},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Sparsification --- A technique for speeding up dynamic graph algorithms}},
  author = {Peter B. Gibbons},
  number = {98k:68039},
  year = {1998},
  text = {This paper makes a major contribution to the study of dynamic graph
    algorithms that maintain some property of a changing graph more efficiently
    than recomputation from scratch after each change. Dynamic algorithms
    can be classified as fully dynamic, where both edge insertions and deletions
    are allowed, or as partially dynamic where only insertions are allowed.
    The improved performances for dynamic algorithms are achieved through
    the use of the new technique of sparsification which, when applicable,
    can speed up a $T(n,m)$ time bound for a graph $G$ with $n$ vertices
    and $m$ edges to $T(n,O(n))$, almost the time needed if $G$ were sparse.
    Sparsification involves partitioning the edges of $G$ into a collection
    of $O(m/n)$ sparse subgraphs, each with $n$ vertices and $O(n)$ edges.
    The information relevant for each subgraph can be summarised in an even
    sparser subgraph, called a sparse certificate. Certificates are merged
    in pairs, producing larger subgraphs which are made sparse again by computing
    their certificates. The result is a balanced binary tree in which each
    node is represented by a sparse certificate. Each update involves $\log
    (m/n)$ graphs with $O(n)$ edges each, instead of one graph with $m$ edges.
    A more careful partition into subgraphs causes each update to involve
    a sequence of graphs with $O(n)$ edges in total. Three variants of the
    sparsification technique are developed. The first is used in situations
    where no previous fully dynamic algorithm was known and gives time bounds
    of $O(n)$ per update. The second variant uses a dynamic data structure
    to maintain certificates possessing a stability property, thereby transforming
    time bounds of the form $O(m\sp p)$ into $O(n\sp p)$. In the third variant,
    deletions are performed as in the first variant, and insertions by using
    a partially dynamic algorithm. This leads to insertion times often matching
    those of known partially dynamic algorithms, together with deletion times
    similar to those of the first variant. Results include the maintenance
    of minimum spanning forests, graph connectivity, graph 2-edge connectivity
    and bipartiteness in time $O(n\sp {1/2})$ per change; 3-edge connectivity
    in time $O(n\sp {2/3})$ per change; 4-edge connectivity in time $O(n\alpha(n))$
    per change; $k$-edge connectivity for constant $k$ in time $O(n\log n)$
    per change; 2-vertex connectivity and 3-vertex connectivity in time $O(n)$
    per change; and 4-vertex connectivity in time $O(n\alpha(n))$ per change.
    Further results speed up the insertion times to match the bounds of known
    partially dynamic algorithms. The paper concludes with sections on recent
    related work and remaining open questions.}}

@techreport{EppGalGia-TR-88,
  title = {{Speeding up dynamic programming}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo},
  address = {New York, NY, 10027, USA},
  institution = {Columbia Univ., Computer Science Dept.},
  number = {CUCS-327-88},
  year = {1988}}

@inproceedings{EppGalGia-FOCS-88,
  title = {{Speeding up dynamic programming}},
  author = {David Eppstein and Zvi Galil and Raffaele Giancarlo},
  booktitle = {Proc. 29th Symp. Foundations of Computer Science},
  publisher = {IEEE},
  pages = {488--496},
  month = {October},
  year = {1988},
  url = {http://www.ics.uci.edu/~eppstein/pubs/EppGalGia-FOCS-88.pdf}}

@techreport{Epp-TR-94-25,
  title = {{Subgraph isomorphism in planar graphs and related problems}},
  author = {David Eppstein},
  eprint = {cs.DS/9911003},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {94-25},
  year = {1994},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-94-25.pdf}}

@inproceedings{Epp-SODA-95,
  title = {{Subgraph isomorphism in planar graphs and related problems}},
  author = {David Eppstein},
  eprint = {cs.DS/9911003},
  booktitle = {Proc. 6th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {632--640},
  month = {January},
  year = {1995},
  review = {MR-95m:05178}}

@article{MR-95m:05178,
  reviews = {Epp-SODA-95},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Subgraph isomorphism in planar graphs and related problems}},
  number = {95m:05178},
  year = {1995}}

@article{Epp-JGAA-99,
  title = {{Subgraph isomorphism in planar graphs and related problems}},
  author = {David Eppstein},
  eprint = {cs.DS/9911003},
  journal = {J. Graph Algorithms {\&} Applications},
  volume = {3},
  number = {3},
  pages = {1--27},
  year = {1999},
  review = {MR-2001b-05154}}

@article{MR-2001b-05154,
  reviews = {Epp-JGAA-99},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Subgraph isomorphism in planar graphs and related problems}},
  author = {Paul Klingsberg},
  volume = {2001b},
  number = {05154},
  year = {2001},
  text = {The subgraph isomorphism problem is the following. Given a graph
    $G$ and another graph $H$, one must determine whether $G$ has a subgraph
    that is isomorphic to $H$. In this fully general form, the problem is
    NP-complete; but if $H$ is a fixed $l$-vertex graph, as the author points
    out, this problem can clearly be solved in $O(n\sp l)$ time, where $n$
    is the number of vertices of $G$. In the current paper, it is assumed
    that $G$ and $H$ are planar; and in this case the author develops an
    algorithm that requires only $O(C\sb Hn)$ time (although the constant
    $C\sb H$ grows exponentially with $l$---necessarily so, if $\rm P\ne
    NP$). 
    
    The main idea behind the algorithm is that of constructing a cover $\{G\sb
    i\}$ for a planar graph $G$ and providing a so-called "tree decomposition"
    for each element $G\sb i$ of the cover. (A tree decomposition of a graph
    $G$ is a tree $T$ with these properties: (1) each node $N$ of $T$ is
    provided with a label $L(N)\subseteq V(G)$; (2) for each $v\in V(G)$,
    the set of tree nodes whose labels contain $v$ forms a contiguous subtree
    of $T$; and (3) for each edge $\{v,w\}$ of $G$, there is at least one
    node $N$ of $T$ such that both $v$ and $w$ are in $L(N)$.) Specifically,
    for an $n$-vertex planar graph $G$, the author shows how, for any positive
    integer $w$, to do the following in $O(w\sp 2n)$ time. He covers $G$
    with a collection of subgraphs $\{G\sb i\}$, so that each vertex of $G$
    is included in at most $w$ of the $\{G\sb i\}$; he provides for each
    $G\sb i$ a tree decomposition in which all labels have $\le(3w-2)$ elements;
    and he partitions $V(G)$ into subsets $\{S\sb i\}$ in such a way that,
    for any connected $w$-vertex subgraph $H$ of $G$, if $i$ is the smallest
    value for which $H\cap S\sb i$ is nonempty, then $H$ is a subgraph of
    $G\sb i$ but is not a subgraph of $G\sb j$ for any $j>i$. The main result,
    an algorithm for deciding the isomorphism question in linear time, is
    then based on dynamic programming in the trees associated to the subgraphs
    $\{G\sb i\}$. 
    
    The author also uses this technique to construct efficient algorithms
    for a number of other decision and enumeration problems for planar graphs,
    including connectivity, diameter, girth, induced subgraph isomorphism,
    and shortest path.}}

@misc{cs.DS/9911003,
  title = {{Subgraph isomorphism in planar graphs and related problems}},
  author = {David Eppstein},
  eprint = {cs.DS/9911003},
  howpublished = {ACM Computing Research Repository},
  month = {November},
  year = {1999}}

@techreport{Epp-TR-91-61,
  title = {{Subquadratic nonobtuse triangulation of convex polygons}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {91-61},
  year = {1991}}

@misc{math.MG/9909152,
  title = {{Tangent spheres and triangle centers}},
  author = {David Eppstein},
  eprint = {math.MG/9909152},
  howpublished = {arXiv.org e-Print archive},
  month = {September},
  year = {1999}}

@article{Epp-AMM-01,
  title = {{Tangent spheres and triangle centers}},
  author = {David Eppstein},
  eprint = {math.MG/9909152},
  journal = {American Mathematical Monthly},
  publisher = {Amer. Math. Soc.},
  volume = {108},
  number = {1},
  pages = {63--66},
  month = {January},
  year = {2001}}

@article{Epp-MER-95,
  title = {{Ten algorithms for Egyptian fractions}},
  author = {David Eppstein},
  journal = {Mathematica in Education and Research},
  volume = {4},
  number = {2},
  pages = {5--15},
  year = {1995}}

@misc{cs.CG/0307023,
  title = {{Testing bipartiteness of geometric intersection graphs}},
  author = {David Eppstein},
  eprint = {cs.CG/0307023},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2003}}

@inproceedings{Epp-SODA-04-bgig,
  title = {{Testing bipartiteness of geometric intersection graphs}},
  author = {David Eppstein},
  eprint = {cs.CG/0307023},
  booktitle = {Proc. 15th Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {853--861},
  month = {January},
  year = {2004}}

@inproceedings{BerEppGui-ESA-95,
  title = {{The centroid of points with approximate weights}},
  author = {Marshall Wayne Bern and David Eppstein and Leonidas J. Guibas
    and John E. Hershberger and Subhash Suri and Jan Dithmar Wolter},
  booktitle = {Proc. 3rd Eur. Symp. Algorithms (ESA 1995)},
  number = {979},
  editor = {Paul G. Spirakis},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {460--472},
  month = {September},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerEppGui-ESA-95.ps.gz}}

@article{AmeBerEpp-GMIP-98,
  title = {{The crust and the $\beta$-skeleton: combinatorial curve reconstruction}},
  author = {Annamaria Beatrice Amenta and Marshall Wayne Bern and David Eppstein},
  journal = {Graphical Models {\&} Image Processing},
  volume = {60/2},
  number = {2},
  pages = {125--135},
  month = {March},
  year = {1998},
  url = {http://www.cs.utexas.edu/users/amenta/pubs/crust.ps.gz}}

@techreport{Epp-TR-92-76,
  title = {{The diameter of nearest neighbor graphs}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-76},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-76.pdf}}

@techreport{GeEppSmy-TR-99,
  title = {{The distribution of cycle lengths in graphical models for iterative
    decoding}},
  author = {Xianping Ge and David Eppstein and Padhraic Smyth},
  eprint = {cs.DM/9907002},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {99-10},
  year = {1999}}

@misc{cs.DM/9907002,
  title = {{The distribution of cycle lengths in graphical models for iterative
    decoding}},
  author = {Xianping Ge and David Eppstein and Padhraic Smyth},
  eprint = {cs.DM/9907002},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {1999}}

@inproceedings{GeEppSmy-ISIT-2000,
  title = {{The distribution of cycle lengths in graphical models for iterative
    decoding}},
  author = {Xianping Ge and David Eppstein and Padhraic Smyth},
  eprint = {cs.DM/9907002},
  booktitle = {Proc. Int. Symp. Information Theory},
  publisher = {IEEE},
  month = {June},
  year = {2000}}

@article{GeEppSmy-IT-01,
  title = {{The distribution of loop lengths in graphical models for turbo
    decoding}},
  author = {Xianping Ge and David Eppstein and Padhraic Smyth},
  journal = {IEEE Trans. Information Theory},
  publisher = {IEEE},
  volume = {47},
  number = {6},
  pages = {2549--2553},
  month = {September},
  year = {2001},
  review = {MR-2002i:94087}}

@article{MR-2002i:94087,
  reviews = {GeEppSmy-IT-01},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{The distribution of loop lengths in graphical models for turbo
    decoding}},
  number = {2002i:94087},
  year = {2002}}

@inproceedings{BagBhaCha-SPAA-04,
  title = {{The effect of faults on network expansion}},
  author = {Amitabha Bagchi and Ankur Bhargava and Amitabh Chaudhary and
    David Eppstein and Christian Scheideler},
  eprint = {cs.DC/0404029},
  booktitle = {Proc. 16th Symp. Parallelism in Algorithms and Architectures
    (SPAA 2004)},
  publisher = {ACM},
  pages = {286--293},
  year = {2004},
  url = {http://doi.acm.org/10.1145/1007912.1007960}}

@misc{cs.DC/0404029,
  title = {{The effect of faults on network expansion}},
  author = {Amitabha Bagchi and Ankur Bhargava and Amitabh Chaudhary and
    David Eppstein and Christian Scheideler},
  eprint = {cs.DC/0404029},
  howpublished = {ACM Computing Research Repository},
  month = {April},
  year = {2004}}

@article{BerEppYao-IJCGA-91,
  title = {{The expected extremes in a Delaunay triangulation}},
  author = {Marshall Wayne Bern and David Eppstein and Frances F. Yao},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {1},
  number = {1},
  pages = {79--92},
  month = {March},
  year = {1991},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf},
  review = {MR-92e:68189}}

@article{MR-92e:68189,
  reviews = {BerEppYao-IJCGA-91},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{The expected extremes in a Delaunay triangulation}},
  author = {Albrecht H{\"u}bler},
  number = {92e:68189},
  year = {1992}}

@inproceedings{BerEppYao-ICALP-91,
  title = {{The expected extremes in a Delaunay triangulation}},
  author = {Marshall Wayne Bern and David Eppstein and Frances F. Yao},
  booktitle = {Proc. 18th Int. Coll. Automata, Languages, and Programming
    (ICALP 1991)},
  number = {510},
  editor = {Javier Leach Albert and Burkhard Monien and Mario Rodr{\'\i}guez-Artalejo},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {674--685},
  month = {July},
  year = {1991}}

@techreport{Epp-TR-90-45,
  title = {{The farthest point Delaunay triangulation minimizes angles}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {90-45},
  year = {1990},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-90-45.pdf}}

@article{Epp-CGTA-92,
  title = {{The farthest point Delaunay triangulation minimizes angles}},
  author = {David Eppstein},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {1},
  number = {3},
  pages = {143--148},
  month = {March},
  year = {1992},
  url = {http://dx.doi.org/10.1016/S0925-7721(98)00031-5},
  review = {MR-92j:68119}}

@article{MR-92j:68119,
  reviews = {Epp-CGTA-92},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{The farthest point Delaunay triangulation minimizes angles}},
  number = {92j:68119},
  year = {1992}}

@misc{cs.CG/0312056,
  title = {{The geometric thickness of low degree graphs}},
  author = {Christian Alexander Duncan and David Eppstein and Stephen G.
    Kobourov},
  eprint = {cs.CG/0312056},
  howpublished = {ACM Computing Research Repository},
  month = {December},
  year = {2003}}

@inproceedings{DunEppKob-SCG-04,
  title = {{The geometric thickness of low degree graphs}},
  author = {Christian Alexander Duncan and David Eppstein and Stephen G.
    Kobourov},
  eprint = {cs.CG/0312056},
  booktitle = {Proc. 20th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {340--346},
  year = {2004}}

@misc{cs.DS/0402028,
  title = {{The lattice dimension of a graph}},
  author = {David Eppstein},
  eprint = {cs.DS/0402028},
  howpublished = {ACM Computing Research Repository},
  month = {February},
  year = {2004}}

@article{Epp-EJC-05,
  title = {{The lattice dimension of a graph}},
  author = {David Eppstein},
  eprint = {cs.DS/0402028},
  journal = {Eur. J. Combinatorics},
  volume = {26},
  number = {5},
  pages = {585--592},
  month = {July},
  year = {2005},
  url = {http://dx.doi.org/10.1016/j.ejc.2004.05.001}}

@inproceedings{EppLue-RSA-01,
  title = {{The minimum expectation selection problem}},
  author = {David Eppstein and George S. Lueker},
  eprint = {cs.DS/0110011},
  booktitle = {10th Int. Conf. Random Structures {\&} Algorithms},
  month = {August},
  year = {2001}}

@misc{cs.DS/0110011,
  title = {{The minimum expectation selection problem}},
  author = {David Eppstein and George S. Lueker},
  eprint = {cs.DS/0110011},
  howpublished = {ACM Computing Research Repository},
  month = {October},
  year = {2001}}

@article{EppLue-RSA-02,
  title = {{The minimum expectation selection problem}},
  author = {David Eppstein and George S. Lueker},
  eprint = {cs.DS/0110011},
  journal = {Random Structures {\&} Algorithms},
  volume = {21},
  number = {3--4},
  pages = {278--292},
  year = {2002},
  url = {http://dx.doi.org/10.1002/rsa.10061},
  review = {MR-2003m:68054}}

@article{MR-2003m:68054,
  reviews = {EppLue-RSA-02},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{The minimum expectation selection problem}},
  author = {Marc Ulrich Stiller},
  number = {2003m:68054},
  year = {2003},
  text = {The authors discuss the min-min expectation selection problem (and
    variations): selecting $k$ out of $n$ given discrete probability distributions,
    to minimize the expectation of the minimum value resulting when independent
    random variables are drawn from the selected distributions. They show
    NP-completeness (with a fully polynomial time approximation scheme),
    if the number of distinct values in each distribution is a constant greater
    than 2, and NP-hardness to approximate the problem within any constant
    approximation factor, if that number is an arbitrary integer. Finally
    they show that the related max-min problem (maximize the expectation)
    is polynomially solvable for a constant number of values in each distribution.
    
     The article is a very interesting example of demonstrating the interplay
    of probability theory and computer science. The reader should be familiar
    with the concepts of NP-theory, including the issue of approximation
    algorithms for such problems.}}

@inproceedings{EppGooSun-SCG-05,
  title = {{The skip quadtree: a simple dynamic data structure for multidimensional
    data}},
  author = {David Eppstein and Michael T. Goodrich and Jonathan Zheng Sun},
  eprint = {cs.CG/0507049},
  booktitle = {Proc. 21st Symp. Computational Geometry},
  publisher = {ACM},
  pages = {296--305},
  month = {June},
  year = {2005}}

@misc{cs.CG/0507049,
  title = {{The skip quadtree: a simple dynamic data structure for multidimensional
    data}},
  author = {David Eppstein and Michael T. Goodrich and Jonathan Zheng Sun},
  eprint = {cs.CG/0507049},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2005}}

@inproceedings{Epp-WADS-03,
  title = {{The traveling salesman problem for cubic graphs}},
  author = {David Eppstein},
  eprint = {cs.DS/0302030},
  booktitle = {Proc. 8th Worksh. Algorithms and Data Structures (WADS 2003)},
  number = {2748},
  editor = {Frank K. H. A. Dehne and J{\"o}rg-Rudiger Sack and Michiel Smid},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {307--318},
  year = {2003}}

@misc{cs.DS/0302030,
  title = {{The traveling salesman problem for cubic graphs}},
  author = {David Eppstein},
  eprint = {cs.DS/0302030},
  howpublished = {ACM Computing Research Repository},
  month = {February},
  year = {2003}}

@misc{cs.CG/0302027,
  title = {{Tiling space and slabs with acute tetrahedra}},
  author = {David Eppstein and John M. Sullivan and Alper {\"U}ng{\"o}r},
  eprint = {cs.CG/0302027},
  howpublished = {ACM Computing Research Repository},
  month = {February},
  year = {2003}}

@article{EppSulUng-CGTA-04,
  title = {{Tiling space and slabs with acute tetrahedra}},
  author = {David Eppstein and John M. Sullivan and Alper {\"U}ng{\"o}r},
  eprint = {cs.CG/0302027},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {27},
  number = {3},
  pages = {237--255},
  year = {2004},
  url = {http://dx.doi.org/10.1016/j.comgeo.2003.11.003},
  review = {MR-2039173}}

@article{MR-2039173,
  reviews = {EppSulUng-CGTA-04},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Tiling space and slabs with acute tetrahedra}},
  number = {2039173},
  year = {2004}}

@techreport{Epp-TR-92-77,
  title = {{Tree-weighted neighbors and geometric $k$ smallest spanning trees}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {92-77},
  year = {1992},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-77.pdf}}

@article{Epp-IJCGA-94,
  title = {{Tree-weighted neighbors and geometric $k$ smallest spanning trees}},
  author = {David Eppstein},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {4},
  number = {2},
  pages = {229--238},
  month = {June},
  year = {1994},
  review = {MR-95f:05028}}

@article{MR-95f:05028,
  reviews = {Epp-IJCGA-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Tree-weighted neighbors and geometric $k$ smallest spanning trees}},
  author = {Ding-Zhu Du},
  number = {95f:05028},
  year = {1995}}

@article{Epp-Tb-85,
  title = {{Trees in \TeX}},
  author = {David Eppstein},
  journal = {TUGboat},
  publisher = {{\TeX} Users' Group},
  volume = {6},
  number = {1},
  pages = {31},
  year = {1985},
  url = {http://www.ics.uci.edu/~eppstein/pubs/p-ttree.tex.Z}}

@inproceedings{Epp-COMB-01,
  title = {{Triangles and squares}},
  author = {David Eppstein},
  booktitle = {Proc. Euroconf. Combinatorics, Graph Theory, and Applications},
  publisher = {Univ. Aut{\'o}noma de Barcelona, Centre de Recerca Matem{\`a}tica},
  editor = {Jaroslav Ne{\v{s}}etril},
  pages = {114},
  month = {September},
  year = {2001}}

@inproceedings{BerDobEpp-SCG-92,
  title = {{Triangulating polygons without large angles}},
  author = {Marshall Wayne Bern and David P. Dobkin and David Eppstein},
  booktitle = {Proc. 8th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {222--231},
  month = {June},
  year = {1992}}

@article{BerDobEpp-IJCGA-95,
  title = {{Triangulating polygons without large angles}},
  author = {Marshall Wayne Bern and David P. Dobkin and David Eppstein},
  journal = {Int. J. Computational Geometry {\&} Applications},
  volume = {5},
  number = {1--2},
  pages = {171--192},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerDobEpp-IJCGA-95.ps.gz},
  month = {March--June},
  note = {Special issue for 8th SCG},
  review = {MR-96e:68124}}

@article{MR-96e:68124,
  reviews = {BerDobEpp-IJCGA-95},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Triangulating polygons without large angles}},
  author = {de Figueiredo, Luiz Henrique},
  number = {96e:68124},
  year = {1996}}

@article{EppDil-EGM-03,
  title = {{Uninscribable 4-regular polyhedron}},
  author = {David Eppstein and Michael B. Dillencourt},
  journal = {Electronic Geometry Models},
  number = {2003.08.001},
  year = {2003},
  url = {http://www.eg-models.de/2003.08.001/}}

@misc{cs.CG/9908003,
  title = {{Ununfoldable polyhedra}},
  author = {Marshall Wayne Bern and Erik D. Demaine and David Eppstein and
    Eric Heng-Shiang Kuo},
  eprint = {cs.CG/9908003},
  howpublished = {ACM Computing Research Repository},
  month = {August},
  year = {1999}}

@inproceedings{BerDemEpp-CCCG-99,
  title = {{Ununfoldable polyhedra}},
  author = {Marshall Wayne Bern and Erik D. Demaine and David Eppstein and
    Eric Heng-Shiang Kuo},
  eprint = {cs.CG/9908003},
  booktitle = {Proc. 11th Canad. Conf. Computational Geometry},
  month = {August},
  year = {1999},
  url = {http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp38.pdf}}

@techreport{BerDemEpp-TR-99,
  title = {{Ununfoldable polyhedra}},
  author = {Marshall Wayne Bern and Erik D. Demaine and David Eppstein and
    Eric Heng-Shiang Kuo},
  eprint = {cs.CG/9908003},
  address = {Waterloo, Ontario N2L 3G1, CANADA},
  institution = {Univ. of Waterloo, School of Computer Science},
  number = {CS-99-04},
  month = {August},
  year = {1999},
  url = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-99-09/}}

@article{BerDemEpp-CGTA-03,
  title = {{Ununfoldable polyhedra with convex faces}},
  author = {Marshall Wayne Bern and Erik D. Demaine and David Eppstein and
    Eric Heng-Shiang Kuo and Andrea Mantler and Jack Snoeyink},
  journal = {Computational Geometry Theory {\&} Applications},
  volume = {24},
  number = {2},
  pages = {51--62},
  month = {February},
  year = {2003},
  url = {http://dx.doi.org/10.1016/S0925-7721(02)00091-3},
  review = {MR-2003m:52017}}

@article{MR-2003m:52017,
  reviews = {BerDemEpp-CGTA-03},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Ununfoldable polyhedra with convex faces}},
  number = {2003m:52017},
  year = {2003}}

@inproceedings{BerDemEpp-WCG-99,
  title = {{Ununfoldable polyhedra with triangular faces}},
  author = {Marshall Wayne Bern and Erik D. Demaine and David Eppstein and
    Eric Heng-Shiang Kuo and Andrea Mantler and Jack Snoeyink},
  booktitle = {Proc. 4th CGC Worksh. Computational Geometry},
  month = {October},
  year = {1999},
  url = {http://www.cs.jhu.edu/~cgc/abstracts99/old/eric.uptf.ps}}

@article{FerSluEpp-NJC-96,
  title = {{Using sparsification for parametric minimum spanning tree problems}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki and David Eppstein},
  journal = {Nordic J. Computing},
  volume = {3},
  number = {4},
  pages = {352--366},
  year = {1996},
  url = {http://www.ics.uci.edu/~eppstein/pubs/FerSluEpp-NJC-96.pdf},
  month = {Winter},
  note = {Special issue for 5th SWAT}}

@inproceedings{FerSluEpp-SWAT-96,
  title = {{Using sparsification for parametric minimum spanning tree problems}},
  author = {David Fern{\'a}ndez-Baca and Giora Slutzki and David Eppstein},
  booktitle = {Proc. 5th Scandinavian Worksh. Algorithm Theory (SWAT 1996)},
  number = {1097},
  editor = {Rolf G. Karlsson and Andrzej Lingas},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag},
  pages = {149--160},
  month = {July},
  year = {1996},
  url = {http://www.ics.uci.edu/~eppstein/pubs/FerSluEpp-SWAT-96.ps.gz}}

@techreport{DemEppEri-TR-01-72,
  title = {{Vertex-unfoldings of simplicial manifolds}},
  author = {Erik D. Demaine and David Eppstein and Jeffrey Gordon Erickson
    and George W. Hart and Joseph O'Rourke},
  eprint = {cs.CG/0110054},
  organization = {Smith College, Dept. of Computer Science},
  number = {072},
  year = {2001}}

@misc{cs.CG/0110054,
  title = {{Vertex-unfoldings of simplicial manifolds}},
  author = {Erik D. Demaine and David Eppstein and Jeffrey Gordon Erickson
    and George W. Hart and Joseph O'Rourke},
  eprint = {cs.CG/0110054},
  howpublished = {ACM Computing Research Repository},
  month = {October},
  year = {2001}}

@inproceedings{DemEppEri-SCG-02,
  title = {{Vertex-unfoldings of simplicial manifolds}},
  author = {Erik D. Demaine and David Eppstein and Jeffrey Gordon Erickson
    and George W. Hart and Joseph O'Rourke},
  eprint = {cs.CG/0110054},
  booktitle = {Proc. 18th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {237--243},
  month = {June},
  year = {2002}}

@incollection{DemEppEri-WK-03,
  title = {{Vertex-unfoldings of simplicial manifolds}},
  author = {Erik D. Demaine and David Eppstein and Jeffrey Gordon Erickson
    and George W. Hart and Joseph O'Rourke},
  eprint = {cs.CG/0110054},
  booktitle = {Discrete Geometry: In honor of W. Kuperberg's 60th birthday},
  number = {253},
  editor = {Andras Bezdek},
  series = {Pure and Applied Mathematics},
  publisher = {Marcel Dekker},
  pages = {215--228},
  year = {2003},
  review = {MR-2034718}}

@article{MR-2034718,
  reviews = {DemEppEri-WK-03},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Vertex-unfoldings of simplicial manifolds}},
  number = {2034718},
  year = {2004}}

@misc{cs.CG/0107023,
  title = {{Vertex-unfoldings of simplicial polyhedra}},
  author = {Erik D. Demaine and David Eppstein and Jeffrey Gordon Erickson
    and George W. Hart and Joseph O'Rourke},
  eprint = {cs.CG/0107023},
  howpublished = {ACM Computing Research Repository},
  month = {July},
  year = {2001}}

@techreport{DemEppEri-TR-01-71,
  title = {{Vertex-unfoldings of simplicial polyhedra}},
  author = {Erik D. Demaine and David Eppstein and Jeffrey Gordon Erickson
    and George W. Hart and Joseph O'Rourke},
  eprint = {cs.CG/0107023},
  institution = {Smith College, Dept. of Computer Science},
  number = {071},
  month = {July},
  year = {2001}}

@techreport{BerDobEpp-TR-89,
  title = {{Visibility with a moving point of view}},
  author = {Marshall Wayne Bern and David P. Dobkin and David Eppstein and
    Robert L. Grossman},
  address = {35 Olden St., Princeton, NJ, 08544-2087, USA},
  institution = {Princeton Univ., Dept. of Computer Science},
  number = {TR-235-89},
  year = {1989}}

@inproceedings{BerDobEpp-SODA-90,
  title = {{Visibility with a moving point of view}},
  author = {Marshall Wayne Bern and David P. Dobkin and David Eppstein and
    Robert L. Grossman},
  booktitle = {Proc. 1st Symp. Discrete Algorithms},
  publisher = {ACM and SIAM},
  pages = {107--118},
  month = {January},
  year = {1990}}

@article{BerDobEpp-Algo-94,
  title = {{Visibility with a moving point of view}},
  author = {Marshall Wayne Bern and David P. Dobkin and David Eppstein and
    Robert L. Grossman},
  journal = {Algorithmica},
  volume = {11},
  number = {4},
  pages = {360--378},
  month = {April},
  year = {1994},
  review = {MR-94j:68307}}

@article{MR-94j:68307,
  reviews = {BerDobEpp-Algo-94},
  journal = {Mathematical Reviews},
  publisher = {Amer. Math. Soc.},
  title = {{Visibility with a moving point of view}},
  number = {94j:68307},
  year = {1994}}

@techreport{BerEpp-TR-?,
  title = {{Worst-case bounds for subadditive geometric graphs}},
  author = {Marshall Wayne Bern and David Eppstein},
  address = {3333 Coyote Hill Rd., Palo Alto, CA, 94304, USA},
  institution = {Xerox Palo Alto Research Center},
  note = {This paper was never actually published in this form, but was nevertheless
    cited as a Xerox TR by Gao and Steele.}}

@inproceedings{BerEpp-SCG-93,
  title = {{Worst-case bounds for subadditive geometric graphs}},
  author = {Marshall Wayne Bern and David Eppstein},
  booktitle = {Proc. 9th Symp. Computational Geometry},
  publisher = {ACM},
  pages = {183--188},
  month = {May},
  year = {1993},
  url = {http://www.ics.uci.edu/~eppstein/pubs/BerEpp-SCG-93.pdf}}

@techreport{Epp-TR-95-53,
  title = {{Zonohedra and zonotopes}},
  author = {David Eppstein},
  address = {Irvine, CA, 92697-3425, USA},
  institution = {Univ. of California, Irvine, Dept. of Information and Computer
    Science},
  number = {95-53},
  year = {1995},
  url = {http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-95-53.pdf}}

@article{Epp-MER-96,
  title = {{Zonohedra and zonotopes}},
  author = {David Eppstein},
  journal = {Mathematica in Education and Research},
  volume = {5},
  number = {4},
  pages = {15--21},
  year = {1996}}