\begin{thebibliography}{99}

\bibitem{ABMP:matching}
{H.~Alt, N.~Blum, K.~Mehlhorn, M.~Paul: 
``Computing a maximum cardinality matching in a bipartite 
  graph in time {$O(n^{1.5} \sqrt{m/\log n})$}''.
 Information Processing Letters, Vol. 37, No. 4, 237-240, 1991}

\bibitem{AS89}
{C.~Aragon, R.~Seidel: 
``Randomized Search Trees''.
Proc. 30th IEEE Symposium on Foundations of Computer Science, 540-545, 1989}

\bibitem{AHU83} 
{A.V.~Aho, J.E.~Hopcroft, J.D.~Ullman: 
``Data Structures and Algorithms''. 
Addison-Wesley Publishing Company, 1983}

\bibitem{AMO93} 
{R.K.~Ahuja, T.L.~Magnanti, J.B.~Orlin: 
``Network Flows'', Section 10.2. Prentice Hall, 1993}

\bibitem{AVL62} 
{G.M. Adelson-Veslkii, Y.M. Landis: 
``An Algorithm for the Organization of Information''.
Doklady Akademi Nauk, Vol. 146, 263-266, 1962}

\bibitem{BA95}
{I.J.~Balaban: ``An Optimal Algorithm for Finding Segment Intersections''. 
Proc. of the 11th ACM Symposium on Computational Geometry, 211-219, 1995}

\bibitem{BS99}
{B.~Balkenhol, Yu.M.~Shtarkov: ``One attempt of a compression algorithm using
the {BWT}''. 
Preprint 99-133, SFB343, Fac.~of Mathematics, University of Bielefeld, 1999}

\bibitem{B79}
{J.L.~Bentley: ``Decomposable Searching Problems''. Information Processing
Letters, Vol. 8, 244-252, 1979}

\bibitem{Bentley:Multi}
{J.L.~Bentley: ``Multi-dimensional Divide and Conquer''. CACM Vol 23, 214-229, 1980}

\bibitem{Be58}
{R.E.~Bellman: ``On a Routing Problem''. Quart. Appl. Math. 16, 87-90, 1958}

\bibitem{BO79}
{J.L.~Bentley, T.~Ottmann: ``Algorithms for Reporting and Counting
Geometric Intersections''. IEEE Trans. on Computers C 28, 643-647, 1979}

\bibitem{BC72}
{R.~Bayer, E.~McCreight: 
``Organization and Maintenance of Large Ordered Indizes'', 
Acta Informatica, Vol. 1, 173-189, 1972}

\bibitem{BM80} 
{N.~Blum, K.~Mehlhorn: 
``On the Average Number of Rebalancing Operations in Weight-Balanced Trees''. 
Theoretical Computer Science 11, 303-320, 1980}

\bibitem{BMS:ESA}
C.~Burnikel, K.~Mehlhorn, and S.~Schirra:
``How to compute the {V}oronoi diagram of line segments: {T}heoretical
and experimental results''.
In {\em LNCS}, volume 855, pages 227--239. Springer-Verlag Berlin/New
York, 1994. Proceedings of ESA'94.

\bibitem{BFMS:SODA97}
C.~Burnikel, R.~Fleischer, K.~Mehlhorn, and S.~Schirra:
``A strong and easily computable separation bound for arithmetic
expressions involving square roots''.
{\em Proceedings of the 8{th} ACM-SIAM Symposium on Discrete
Algorithms}, 1997.

\bibitem{BFMS:Algorithmica}
C.~Burnikel, R.~Fleischer, K.~Mehlhorn, and S.~Schirra:
``A strong and easily computable separation bound for arithmetic expressions involving radicals��.
Algorithmica, Vol.27, 87-99, 2000.

\bibitem{Burnikel:thesis}
C.~Burnikel.
``Exact Computation of Voronoi Diagrams and Line Segment
Intersections''. PhD thesis, Universit{\"a}t des Saarlandes, 1996.

\bibitem{BWTrafo}
M.~Burrows, D.J.~Wheeler.
``A Block-sorting Lossless Data Compression Algorithm''. 
Digital Systems Research Center Research Report 124, 1994.

\bibitem{CLR90}
{T.H. Cormen, C.E. Leiserson, R.L. Rivest: ``Introduction to Algorithms''. 
MIT Press/McGraw-Hill Book Company, 1990 }

\bibitem{CT76}
{D. Cheriton, R.E. Tarjan: ``Finding Minimum Spanning Trees''.
 SIAM Journal of Computing, Vol. 5, 724-742, 1976}

\bibitem{Cheriyan-Mehlhorn}
{J. Cheriyan and K. Mehlhorn:
``Algorithms for Dense Graphs and Networks on the Random Access Computer''. 
Algorithmica, Vol. 15, No. 6, 521-549, 1996}

\bibitem{De92}
{ O. Devillers: ``Robust and Efficient Implementation of the Delaunay Tree''.
Technical Report, INRIA, 1992}

\bibitem{Di59}
{E.W. Dijkstra: ``A Note on Two Problems in Connection With Graphs''.
 Num. Math., Vol. 1, 269-271, 1959}

\bibitem{DKMMRT88} 
{M.~Dietzfelbinger, A.~Karlin, K.~Mehlhorn, F.~Meyer 
auf der Heide, H.~Rohnert, R.~Tarjan: 
``Upper and Lower Bounds for the Dictionary Problem''.
Proc. of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988}

\bibitem{DSST89}
{J.R.~Driscoll, N.~Sarnak, D.~Sleator, R.E.~Tarjan:
``Making Data Structures Persistent''. 
Proc. of the 18th Annual ACM Symposium on Theory of Computing, 109-121, 1986}

\bibitem{E65}
{J.~Edmonds: ``Paths, Trees, and Flowers''. 
Canad. J. Math., Vol. 17, 449-467, 1965}

\bibitem{Ed82}
{H.~Edelsbrunner: ``Intersection Problems in Computational Geometry''.
Ph.D. thesis, TU Graz, 1982}

\bibitem{EK72}
{J.~Edmonds and R.M.~Karp: 
``Theoretical Improvements in Algorithmic Efficiency for Network Flow
Problems''. Journal of the  ACM, Vol. 19, No. 2, 1972}

\bibitem{EKZ77}
{P.v.~Emde Boas, R.~Kaas, E.~Zijlstra: ``Design and Implementation of an 
Efficient Priority Queue''. Math. Systems Theory, Vol. 10, 99-127, 1977}

\bibitem{fgkss:cgalarticle}
A.~Fabri, G.-J. Giezeman, L.~Kettner, S.~Schirra, and S.~Sch{\"o}nherr:
``The {C}{G}{A}{L} kernel: A basis for geometric computation''.
{\em First ACM Workshop on Applied Computational Geometry}, 1996.

\bibitem{Fa48} 
{I.~Fary: ``On Straight Line Representing of Planar Graphs''. Acta. Sci. Math.
 Vol. 11, 229-233, 1948}

\bibitem{Fe96}
{P.~Fenwick: ``Block Sorting Text Compression - Final Report''. 
Tech.~Rep.~130, Dep.~of Comp.~Science, University of Auckland, 1996}

\bibitem{Fl62}
{R.W.~Floyd: ``Algorithm 97: Shortest Paths''. Communcication of the ACM,
 Vol. 5, p. 345, 1962}

\bibitem{Ford-Fulkerson} 
{L.R.~Ford, D.R.~Fulkerson:
``Flows in Networks''.
Princeton Univ. Press, 1963}

\bibitem{Fortune-vWijk}
S.~Fortune and C.~{van Wyk}:
``Efficient exact arithmetic for computational geometry''.
{\em Proc. of the 9th Symp. on Computational Geometry}, 
 163--171, 1993.

\bibitem{FT87} 
{M.L.~Fredman, and R.E.~Tarjan: 
``Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms''.
Journal of the ACM, Vol. 34, 596-615, 1987}

\bibitem{G74} 
{H.N.Gabow: 
``Implementation of algorithms for maximum matching on nonbipartite graphs''. 
Ph.D. thesis, Stanford Univ., Stanford, CA, 1974}

\bibitem{Gabow: Edmonds} 
{H.N.Gabow: 
``An efficient implementation of {E}dmond's algorithm for 
maximum matching on graphs''. 
Journal of the ACM, Vol. 23, 221-234, 1976}

\bibitem{bs:GHJV95a}
{E.~Gamma, R.~Helm, R.~Johnson, and J.~Vlissides:
 {\em Design patterns}.
 Addison-Wesley Publishing Company, 1995}

\bibitem{GK79}
{A. Goralcikova, V. Konbek: ``A Reduct and Closure Algorithm for Graphs''.
Mathematical Foundations of Computer Science, LNCS 74, 301-307, 1979}

\bibitem{GOP90}
{K.E.~Gorlen, S.M.~Orlow, P.S.~Plexico: ``Data Abstraction and Object-Oriented
Programming in \CC''. John Wiley \& Sons, 1990}

\bibitem{GS78}
{L.J.~Guibas, R.~Sedgewick: `` A Dichromatic Framework for Balanced Trees''.
Proceedings of the 19th IEEE Symposium on Foundations of Computer Science,
8-21, 1978}

\bibitem{GT88}
{Goldberg, R.E.~Tarjan: 
``A New Approach to the Maximum Flow Problem''.
Journal of the ACM, Vol. 35, 921-940, 1988 }

\bibitem{HK73}
{J.E.~Hopcroft, R.M.~Karp: 
``An $O(n^{2.5})$ Algorithm for Matching in Bipartite Graphs''. 
SIAM Journal of Computing, Vol. 4, 225-231, 1973}

\bibitem{HT74}
{J.E.~Hopcroft, R.E.~Tarjan: 
``Efficient Planarity Testing''. Journal of the ACM, Vol. 21, 549-568, 1974}

\bibitem{HI97}
M.~Himsolt: ``GML: A portable Graph File Format''. Technical Report, 
Universit{\"a}t Passau, 1997, cf.
\texttt{http://www.fmi.uni-passau.de/\~himsolt/Graphlet/GML}

\bibitem{HU89}
{T.~Hagerup, C.~Uhrig: ``Triangulating a Planar Map Without Introducing
 multiple Arcs'', unpublished, 1989 }

\bibitem{Huffman52}
{D.A.~Huffman: ``A Method for the Construction of Minimum Redundancy Codes''.
Proc. IRE 40, 1098-1101, 1952}

\bibitem{IK03}
{T.~Iwata, K.~Kurosawa: ``OMAC: One-Key CBC MAC''. 
Proc. Fast Software Encryption (FSE), LNCS 2887, 129-153, 2003}

\bibitem{Ka62}
{A.B.~Kahn: ``Topological Sorting of Large Networks''. 
Communications of the ACM, Vol. 5, 558-562, 1962}

\bibitem{Knuth-Levy}
D.~Knuth and S.~Levy:
{\em The {CWEB} System of Structured Documentation, Version 3.0}.
Addison-Wesley, 1993.

\bibitem{Kr56}
{J.B.~Kruskal: ``On the Shortest Spanning Subtree of a Graph and the Travelling
 Salesman Problem''. Proc. American Math. Society 7, 48-50, 1956}

\bibitem{p:KNW97} 
{D.~K{\"u}hl, M.~Nissen, K.~Weihe:
 ``Efficient, adaptable implementations of graph algorithms''.
 Workshop on Algorithm Engineering, Venice, Italy, September 15-17, 1997.
 {\tt http://www.dsi.unive.it/\~wae97/proceedings/ONLY\_PAPERS/pap4.ps.gz}}
  
\bibitem{p:KW97b}
{D.~ K{\"u}hl and K.~Weihe: 
 ``Data access templates''.
 {\em C++ Report}, 9/7, 15 and 18-21, 1997}

\bibitem{L76}
{E.L.~Lawler: 
``Combinatorial Optimization: Networks and Matroids''.
Holt, Rinehart and Winston, New York, 1976}

\bibitem{Li89} 
{S.B.~Lippman: ``\CC Primer''. Addison-Wesley, Publishing Company, 1989}

\bibitem{Lu78} 
{G.S.~Luecker: 
``A Data Structure for Orthogonal Range Queries''. 
Proc. 19th IEEE Symposium on Foundations of Computer Science, 28-34, 1978}

\bibitem{M84} 
{K.~Mehlhorn: 
``Data Structures and Algorithms''. Vol. 1--3,
Springer Publishing Company, 1984}

\bibitem{MC80}
{D.M.~McCreight: 
``Efficient Algorithms for Enumerating Intersecting Intervals''.
 Xerox Parc Report, CSL-80-09, 1980}

\bibitem{MC81}
{D.M.~McCreight: 
 ``Priority Search Trees''. 
 Xerox Parc Report, CSL-81-05, 1981}

\bibitem{Mignotte:Buch}
M.~Mignotte: ``Mathematics for Computer Algebra''.
Springer Verlag, 1992.

\bibitem{MN89} 
{K.~Mehlhorn, S.~N{\"a}her: 
``LEDA, a Library of Efficient Data Types and Algorithms''. 
TR A 04/89, FB10, Universit{\"a}t des Saarlandes, 
Saarbr{\"u}cken, 1989}

\bibitem{MN95} 
{K. Mehlhorn, S. N{\"a}her: 
`` LEDA, a Platform for Combinatorial and Geometric Computing''. 
Communications of the ACM, Vol. 38, No. 1, 96-102, 1995 }

\bibitem{LEDAbook} 
K.~Mehlhorn, S.~N{\"a}her:
``{LEDA}, a Platform for Combinatorial and Geometric Computing''.
book, in preparation. For sample chapters see the LEDA www-pages.

\bibitem{Me-Naeher:sweep}
K.~Mehlhorn and S.~N{\"a}her:
``Implementation of a sweep line algorithm for the straight line
segment intersection problem''.
Technical Report MPI-I-94-160, Max-Planck-Institut f\"ur Informatik,
 Saarbr{\"u}cken, 1994.

\bibitem{Me-Naeher:IFIP94}
K.~Mehlhorn and S.~N{\"a}her:
``The implementation of geometric algorithms''.
In {\em 13th World Computer Congress IFIP94}, volume~1, pages
 223--231. Elsevier Science B.V. North-Holland, Amsterdam, 1994.

\bibitem{Mignotte:book}
M.~Mignotte:
Mathematics for Computer Algebra.
Springer Verlag, 1992

\bibitem{MU94}
K.~Mulmuley:
Computational Geometry:
An Introduction Through Randomized Algorithms.
Prentice Hall, 1994

\bibitem{bs:MS95a}
{D.R.~Musser and Atul Saini.
 {\em STL Tutorial and Reference Guide}.
 Addison-Wesley Publishing Company, 1995}

\bibitem{N90}
S.~N{\"a}her:
``LEDA2.0  User Manual''.
Technischer Bericht A 17/90, Fachbereich Informatik.
Universit{\"a}t des Saarlandes, Saarbr{\"u}cken, 1990

\bibitem{Ni99}
{M.~Nissen:
``Design Pattern Data Accessor''. Proceedings of the EuroPLoP 1999.}

\bibitem{p:N98} 
{M.~Nissen. Graph Iterators: 
 ``Decoupling Graph Structures from Algorithms'' (masters thesis). 
 {\tt http://www.mpi-sb.mpg.de/\~marco/diplom.ps.gz}}

\bibitem{p:NW96} 
{M.~Nissen, K.~Weihe:
 ``Combining LEDA with customizable implementations of graph algorithms''.
 Konstanzer Schriften in Mathematik und Informatik (no. 17),
 Universit\"at Konstanz, 1996. Available at
 {\tt ftp://ftp.informatik.uni-konstanz.de/pub/preprints/}}

\bibitem{p:NW98} 
{M.~Nissen, K.~Weihe: ``Attribute classes in Java and language
 extensions''. Konstanzer Schriften in Mathematik und Informatik (no. 66),
 Universit\"at Konstanz, 1998. Available at
 {\tt ftp://ftp.informatik.uni-konstanz.de/pub/preprints/}}

\bibitem{over:cgalarticle}
{M.~H. Overmars:
Designing the computational geometry algorithms library {C}{G}{A}{L}.
{\em In Proceedings First ACM Workshop on Applied Computational Geometry}, 
1996}

\bibitem{PS85} 
{F.P.~Preparata, M.I.~Shamos: 
``Computational Geometry: An Introduction''. 
Springer Publishing Company, 1985}

\bibitem{Pugh}
{W.~Pugh: 
``Skip Lists: A Probabilistic Alternative to Balanced Trees''.
Communications of the ACM, Vol. 33, No. 6, 668-676, 1990} 

\bibitem{Ramsey:noweb}
{N.~Ramsey: ``Literate programming simplified''.
{\em IEEE Software}, pages 97--105, 1994}

\bibitem{S-04}
{S.~Schmitt: ``Improved separation bounds for the diamond operator''.
{\em Technical Report ECG-TR-36-31-08-01}, 2004}

\bibitem{Schneier} 
{B.~Schneier: 
``Applied Cryptography, Second Edition''.
John Wiley and Sons, 1996}
\bibitem{Shk02}
{D.~Shkarin: 
``PPM: one step to praticality''.
Proc. IEEE Data Compression Conf. (DCC'2002), 202-211, 2002}

\bibitem{SW94}
{M.~Stoer and F.~Wagner: 
``A Simple Min Cut Algorithm''.
Algorithms -- ESA '94, LNCS 855, 141-147, 1994}

\bibitem{S91} 
{B.~Stroustrup: 
``The \CC Programming Language, Second Edition''.
Addison-Wesley Publishing Company, 1991}

\bibitem{SV87}
{J.T.~Stasko, J.S.~Vitter: 
``Pairing Heaps: Experiments and Analysis''.
 Communications of the ACM, Vol. 30, 234-249, 1987}

\bibitem{T72}
{R.E.~Tarjan: 
``Depth First Search an Linear Graph Algorithms''.
SIAM Journal of Computing, Vol. 1, 146-160, 1972}

\bibitem{T83} 
{R.E.~Tarjan: 
``Data Structures and Network Algorithms''.
CBMS-NSF Regional Conference Series in Applied Mathematics,
Vol. 44, 1983}

\bibitem{Vi89} 
{J.S.~Vitter: 
``Dynamic Huffman Coding''.
ACM Transactions on Mathematical Software, Vol.~15, No.~2, 158-167,
1989}

\bibitem{We92} 
{M.~Wenzel: 
``W{\"o}rterb{\"u}cher f{\"u}r ein beschr{\"a}nktes Universum''.
Diplomarbeit, Fachbereich Informatik, Universit{\"a}t des Saarlandes,
1992}

\bibitem{Whi73}
{A.G.~White: 
``Graphs,Groups, and Surfaces''.
North Holland, 1973}

\bibitem{Wi85}
{D.E.~Willard: 
``New Data Structures for Orthogonal Queries''.
SIAM Journal of Computing, 232-253, 1985}

\bibitem{Wi64}
{J.W.J.~Williams:
``Algorithm 232 (heapsort)��.
Communications of the ACM, Vol. 7, 347-348, 1964}

\bibitem{WRC:arith-coding}
{I.H.~Witten, M.~Radford and J.G.~Cleary: 
``Arithmetic Coding for Data Compression''.
Communications of the ACM, Vol. 30, 520-540, 1987}

\bibitem{LZ77}
{J.~Ziv and A.~Lempel:
``A universal algorithm for sequential data compression''.
IEEE Transactions on Information Theory, Vol. 30(3), 337-343, 1977}

\bibitem{LZ78}
{J.~Ziv and A.~Lempel:
``Compression of individual sequences via variable-rate coding''
IEEE Transactions on Information Theory, Vol. 24(5), 530-536, 1978}

\bibitem{NZ02}
{S.~N\"aher, O.~Zlotowski:
``Design and Implementation of Data Types for Static Graphs''.
ESA, 2002}

\end{thebibliography}
