  The efficiency of extracting topological information from point data depends
largely on the complex that is built on top of the data points. From a
computational viewpoint, the most favored complexes for this purpose have so
far been Vietoris-Rips and witness complexes. While the Vietoris-Rips complex
is simple to compute and is a good vehicle for extracting topology of sampled
spaces, its size is huge--particularly in high dimensions. The witness complex
on the other hand enjoys a smaller size because of a subsampling, but fails to
capture the topology in high dimensions unless imposed with extra structures.
We investigate a complex called the {\em graph induced complex} that, to some
extent, enjoys the advantages of both. It works on a subsample but still
retains the power of capturing the topology as the Vietoris-Rips complex. It
only needs a graph connecting the original sample points from which it builds a
complex on the subsample thus taming the size considerably. We show that, using
the graph induced complex one can (i) infer the one dimensional homology of a
manifold from a very lean subsample, (ii) reconstruct a surface in three
dimension from a sparse subsample without computing Delaunay triangulations,
(iii) infer the persistent homology groups of compact sets from a sufficiently
dense sample. We provide experimental evidences in support of our theory.
