Approximating Densest Subgraph in Geometric Intersection Graphs

$ {}[1]{| {#1} |}% {}{{G}}% {}{}% {}{}% {}{{H}}% {}{{H}}% {}{{V}}% {}[1]{{#1}}% {}{{E}}% {}{{E}}% {}{R} {}{R} {}{X} {}{r} {}[1]{#1} {}{q} {}{ε} {}[1]{V {#1}} {}{P} {}[1]{[ #1 ]} {}{m̄} {}[2][\!]{#1({#2})} {}{polylog} {}{ N} {}{ Z} {}{p} {}[2]{\| {#1} - {#2} \|} {}{q} {}{s}$ For an undirected graph $G=(V, E)$, with $n$ vertices and $medges, the densest subgraph problem, is to compute a subsetS ⊆ V$ which maximizes the ratio $|E_S| / |S|$, where $E_S ⊆ E$ is the set of all edges of $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 $Ω(m)$ time. We present near-linear time (in $n$) approximation algorithms for the densest subgraph problem on 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.