Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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.

share|cite|improve this question
I have a feeling this is going to take more than graph theory. For example, if you take a long chain of these cells and consider the corresponding subgraph, it will still be planar. Perhaps what might work better is considering the points that locally maximize the distance to the nearest grain as the centers of the cells. – Rahul Jul 29 '12 at 11:09
@RahulNarain Lots of irrelevant subgraphs will be planar, it is true, and these multi-cell surfaces will be topologically spherical too. But we should be able to test if they are subdivisible, or something. I appreciate that geometry may have to be reintroduced in order to solve the problem, although we'd have to add 'lengths' to the edges rather than label the cells in advance, as the point of the computation is to discover the cells. Thanks for your comments, they are helpful! PS is 'topologically spherical' the right term to use here? – tehwalrus Jul 29 '12 at 12:54
So, I'm not sure what exactly is meant by a "cell". Where does one region of space stop being in one cell and start being in another cell? – Nick Alger Jul 30 '12 at 8:26
My suggestion does attempt to discover the cells. More precisely, I'm proposing to take as input only a set of points in $\mathbb R^3$ (the grain locations), and then "discover" potential cells as the locally largest spheres that do not contain any of the points. But then again, this ignores the connectivity of the graph entirely, so it's probably not what you want. – Rahul Jul 30 '12 at 8:58
@RahulNarain Ah, I see - sorry, I misunderstood. A colleague actually tried that approach before (or something similar) and it leads to errors and edge cases. – tehwalrus Jul 30 '12 at 9:44
up vote 1 down vote accepted

This problem has been solved by Hilpert and Glantz, whose solution is rather complex, and is not pure graph theory, but a branch of it which focusses on geometrical graphs. The geometry of the system is fundamental to the problem; it cannot be solved on the adjacency alone.

Approximately, it involves finding the 3D Voronoi and Delaunay tessellations of the pore space (a subspace of $\mathbb{R}^3$,) which is possible only under some constraints, and from there it is possible to deduce (from edge/face intersection between these two dual networks) which are the 'throats,' and by another geometrical test to collapse the tessellating elements into their parents to obtain volume-filling cells and polygonal surfaces representing the throats between them.

Their software implementation is also available on the site.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.