One family of graphs that bears unlimited degrees of computational fruit has been dubbed (by me) *painted and rooted cacti* (PARCs).  *Painted* just means that you can associate any subset of a finite *palette* $\mathcal{P} = \lbrace p_1, \ldots, p_k \rbrace $ of *colors* $p_j$ with each node of the underlying rooted cactus.

PARCs can be interpreted as propositional calculus formulas in a couple of ways that are logically dual to each other, extending the graphical syntax for propositional logic that C.S. Peirce called his Alpha graphs, with their *entitative* and *existential* readings.

I'll dig up some links …

I'd completely forgotten — here's a [sparse exposition of cactus calculus][1] (in the so-called *existential interpretation*) that I'd already posted on another question.

  [1]: https://mathoverflow.net/questions/4930/finding-minimal-or-canonical-expressions-for-boolean-truth-tables/4979#4979