  Motivated by understanding the quality of tractable convex relaxations of
intractable polytopes, Ko et al. gave a closed-form expression for the volume
of a standard relaxation $\mathscr{Q}(G)$ of the boolean quadric polytope (also
known as the (full) correlation polytope) $\mathscr{P}(G)$ of the complete
graph $G=K_n$. We extend this work to structured sparse graphs, giving: (i) an
efficient algorithm for $vol(\mathscr{Q}(G))$ when $G$ has bounded tree width,
(ii) closed-form expressions (and asymptotic behaviors) for
$vol(\mathscr{Q}(G))$ for all stars, paths, and cycles, and (iii) a closed-form
expression for $vol(\mathscr{P}(G))$ for all cycles. Further, we demonstrate
that when $G$ is a cycle, the simple relaxation $\mathscr{Q}(G)$ is a very
close model for the much more complicated $\mathscr{P}(G)$. Additionally, we
give some computational results demonstrating that this behavior of the cycle
seems to extend to more complicated graphs. Finally, we speculate on the
possibility of extending some of our results to cactii or even series-parallel
graphs.
