I'm not sure you want subgraphs, either. Succinct circuits encode exponential-sized graphs in poly space. I read a little on this, and I realize I've seen exa

I'm not sure you want subgraphs, either. Succinct circuits encode exponential-sized graphs in poly space. I read a little on this, and I realize I've seen examples of succinct circuits. Hash functions are a great example of poly-sized circuits that compute the edges of exponentially-large graphs (fixing the input size to the output size, for example). Want to find the edge-reversal of that graph? It'll cost ya.