Finding a graph-theoretic representation of expressions in Boole's algebra
A bit of shameless self-promotion, but you might find http://www.sciencedirect.com/science/article/pii/0895717794001669 relevant, as well as the earlier paper I cite there by Frank Harary. 

Those papers present the idea that a boolean function can be represented as a hypercube in which the vertices represent combinations of truth values. That is, rather than construct a graph with a vertex for each boolean variable X, Y etc, construct a graph where one vertex represents the tuple &lt;X=0,Y=0&gt;, one represents &lt;X=0,Y=1&gt; etc.