  Motivated by applications in distributed storage, the storage capacity of a
graph was recently defined to be the maximum amount of information that can be
stored across the vertices of a graph such that the information at any vertex
can be recovered from the information stored at the neighboring vertices.
Computing the storage capacity is a fundamental problem in network coding and
is related, or equivalent, to some well-studied problems such as index coding
with side information and generalized guessing games. In this paper, we
consider storage capacity as a natural information-theoretic analogue of the
minimum vertex cover of a graph. Indeed, while it was known that storage
capacity is upper bounded by minimum vertex cover, we show that by treating it
as such we can get a 3/2 approximation for planar graphs, and a 4/3
approximation for triangle-free planar graphs. Since the storage capacity is
intimately related to the index coding rate, we get a 2 approximation of index
coding rate for planar graphs and 3/2 approximation for triangle-free planar
graphs. We also show a polynomial time approximation scheme for the index
coding rate when the alphabet size is constant. We then develop a general
method of "gadget covering" to upper bound the storage capacity in terms of the
average of a set of vertex covers. This method is intuitive and leads to the
exact characterization of storage capacity for various families of graphs. As
an illustrative example, we use this approach to derive the exact storage
capacity of cycles-with-chords, a family of graphs related to outerplanar
graphs. Finally, we generalize the storage capacity notion to include recovery
from partial node failures in distributed storage. We show tight upper and
lower bounds on this partial recovery capacity that scales nicely with the
fraction of failures in a vertex.
