David Eppstein (Дэвид Эппштейн). Список публикаций. Часть A-D

3-coloring in time $O(1.3289^n)$

@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}}

3-coloring in time $O(1.3446^n)$: a no-MIS algorithm

@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}}

A deterministic linear time algorithm for geometric separators and its applications

@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}}

A disk-packing algorithm for an origami magic trick

@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)].}}

A heuristic approach to program inversion

@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}}

A steady state model for graph power laws

@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}}

Acute square triangulation

@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/}}

Algorithms for coloring quadtrees

@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}}

Algorithms for drawing media

@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}}

Algorithms for media

@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}}

Algorithms for proximity problems in higher dimensions

@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}}

All maximal independent sets and dynamic dominance for sparse graphs

@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}}

An efficient algorithm for shortest paths in vertical and horizontal segments

@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}}

Approximating center points with iterated Radon points

@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}}

Approximating the minimum weight Steiner triangulation

@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}}

Approximation algorithms for geometric problems

@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}}

Arboricity and bipartite subgraph listing algorithms

@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}}

Asymptotic speed-ups in constructive solid geometry

@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}}

Average case analysis of dynamic geometric optimization

@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}}

Beta-skeletons have unbounded dilation

@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}}

Choosing subsets with maximum weighted average

@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}}

Clustering for faster network simplex pivots

@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}}

Comment on Location-Scale Depth

@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}}

Computing the depth of a flat

@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}}

Computing the discrepancy

@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}}

Computing the discrepancy with applications to supersampling patterns

@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}}

Confluent drawings: visualizing non-planar diagrams in a planar way

@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}}

Confluent layered drawings

@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}}

Connectivity, graph minors, and subgraph multiplicity

@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}}

Delta-confluent drawings

@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.}}

Deterministic sampling and range counting in geometric data streams

@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}}

Diameter and treewidth in minor-closed graph families

@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.}}

Dihedral bounds for mesh generation in high dimensions

@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}}

Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees

@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}}

Dynamic connectivity in digital images

@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}}

Dynamic Euclidean minimum spanning trees and extrema of binary functions

@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}}

Dynamic generators of topologically embedded graphs

@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}}

Dynamic graph algorithms

@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}}

Dynamic three-dimensional linear programming

@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}}