  $ \newcommand{\cardin}[1]{\left| {#1} \right|}%
\newcommand{\Graph}{\Mh{\mathsf{G}}}% \providecommand{\G}{\Graph}%
\renewcommand{\G}{\Graph}% \providecommand{\GA}{\Mh{H}}%
\renewcommand{\GA}{\Mh{H}}% \newcommand{\VV}{\Mh{\mathsf{V}}}%
\newcommand{\VX}[1]{\VV\pth{#1}}% \providecommand{\EE}{\Mh{\mathsf{E}}}%
\renewcommand{\EE}{\Mh{\mathsf{E}}}% \newcommand{\Re}{\mathbb{R}}
\newcommand{\reals}{\mathbb{R}} \newcommand{\SetX}{\mathsf{X}}
\newcommand{\rad}{r} \newcommand{\Mh}[1]{#1} \newcommand{\query}{q}
\newcommand{\eps}{\varepsilon} \newcommand{\VorX}[1]{\mathcal{V} \pth{#1}}
\newcommand{\Polygon}{\mathsf{P}} \newcommand{\IntRange}[1]{[ #1 ]}
\newcommand{\Space}{\overline{\mathsf{m}}}
\newcommand{\pth}[2][\!]{#1\left({#2}\right)}
\newcommand{\polylog}{\mathrm{polylog}} \newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z} \newcommand{\pt}{p} \newcommand{\distY}[2]{\left\|
{#1} - {#2} \right\|} \newcommand{\ptq}{q} \newcommand{\pts}{s}$ For an
undirected graph $\mathsf{G}=(\mathsf{V}, \mathsf{E})$, with $n$ vertices and
$m$ edges, the \emph{densest subgraph} problem, is to compute a subset $S
\subseteq \mathsf{V}$ which maximizes the ratio $|\mathsf{E}_S| / |S|$, where
$\mathsf{E}_S \subseteq \mathsf{E}$ is the set of all edges of $\mathsf{G}$
with endpoints in $S$. The densest subgraph problem is a well studied problem
in computer science. Existing exact and approximation algorithms for computing
the densest subgraph require $\Omega(m)$ time. We present near-linear time (in
$n$) approximation algorithms for the densest subgraph problem on
\emph{implicit} geometric intersection graphs, where the vertices are
explicitly given but not the edges. As a concrete example, we consider $n$
disks in the plane with arbitrary radii and present two different approximation
algorithms.
