Update/clarification: I'm looking for an elegant problem definition, not necessarily a solution, so please feel free to answer in that vein. (also check the end for additional clarifications)
NOTE: I am trying to solve a granular physics problem which is fundamentally topological, and should be simple in graph theory if I can get the jargon terms right. However, as it has a geometrical starting point and I am a physicist not a mathematician, I don't even know how to state the problem succinctly. Thus, I am asking for either help stating the problem, in order to be able to research it properly, or known solutions to the problem, if they already exist.
Imagine a pile of spherical grains stacked in a disordered arrangement (in mechanical equilibrium in both force and torque). Which grains are touching which others is a sparse non-planar connectivity graph.
Now imagine being inside this granular structure, but not inside one of the spheres, and looking around. You will be in a cavity (call it a "cell") which is bounded by some grains, but you can see through the gaps in the grains to the adjacent cells. If we replace the grains by their vertices, and contacts points by edges, you can see that you are inside a topologically spherical planar subgraph, and by looking through the loops on the sphere-like surface you can see through to the adjacent cells, which are topologically similar.
Now, what I want to be able to do is to find all such cells from the granular connectivity graph computationally. I can handle defining my graph from a sparse adjacency matrix, and I can handle everything else I need to do once I have the cells as subgraphs, but I need to know what the mathematical names for my cells are ("the set of maximal planar subgraphs" would be a guess, but these wouldn't all be topologically spherical surely?) so that I can find algorithms to compute them, or existing implementations in something like sage.graphs
.
This could also be described as a 3D analogue of a dual (the dual graph being the cell centres connected through the grain network's edge loops), although since neither graph is planar this is emphatically not a proper dual; it's just a bit like one conceptually.
I would be grateful for clarification questions in the comments, if you need more information to understand the problem.
UPDATE 2:
I was half way through writing my own answer to this along the lines of 'give up', having concluded that the problem is irreducibly geometrical, and very slow to compute, when I had a revelation which may help reclassify the problem.
Compare a valid granular graph to a random sparse graph with the same average number of edges per vertex (coordination number). If we compute a depth-first search from a random grain $g_i$ along the graphs, and limited the depth of our search to 4 or 5, we would get very different results. In general, the random graph would yield some potentially high fraction of the vertices (this fraction could be estimated, and would presumably be a function of the depth limit and the coordination number) but the granular graph would give us a very small and specific subset of vertices; the ones that were spatially correlated${}^\dagger$.
If the granular graph has some simplifying property, call it spatial correlation, does this simplify the problem for non-spatial analysis? Does this type of graph have a name, and it's own set of simplified results and algorithms? Either would be helpful; intuitively I could see this this helping to simplify the problem algorithmically, and possibly even mathematically.
${}^\dagger$ NOTE: This correlation assumes only small polydispersity; that is, it assumes the grains are of the same order of magnitude of size. Ideally, this would not be a constraint on the analysis, but if it helps make a worse-than-NP-complete problem easier, then it's worth it (finding the cells, or say even the loops on the surface of cells, involves finding all loops and then filtering them in some additional non-trivial calculation.)
Further note, much later:
I am still working on this problem, although it's looking a lot more like a computational hack than a nice piece of mathematics. Even so, I'll post an update answer when I have something to say.