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 …