  Complex networks have become increasingly popular for modeling various
real-world phenomena. Realistic generative network models are important in this
context as they avoid privacy concerns of real data and simplify complex
network research regarding data sharing, reproducibility, and scalability
studies. \emph{Random hyperbolic graphs} are a well-analyzed family of
geometric graphs. Previous work provided empirical and theoretical evidence
that this generative graph model creates networks with non-vanishing clustering
and other realistic features. However, the investigated networks in previous
applied work were small, possibly due to the quadratic running time of a
previous generator.
  In this work we provide the first generation algorithm for these networks
with subquadratic running time. We prove a time complexity of $O((n^{3/2}+m)
\log n)$ with high probability for the generation process. This running time is
confirmed by experimental data with our implementation. The acceleration stems
primarily from the reduction of pairwise distance computations through a polar
quadtree, which we adapt to hyperbolic space for this purpose. In practice we
improve the running time of a previous implementation by at least two orders of
magnitude this way. Networks with billions of edges can now be generated in a
few minutes.
  Finally, we evaluate the largest networks of this model published so far. Our
empirical analysis shows that important features are retained over different
graph densities and degree distributions.
