At WADS last summer Jeff Erickson gave a nice talk about Rips complexes, which I also posted about here a while back, and last month Jeff and his co-authors posted their preprint to the arxiv, at which point I dumped it in my folder of recent arxiv preprints that I should really read and try to understand someday. But then it was the holidays and I got busy with other stuff and I didn't get around to looking at it until now, when Jeff and his student Erin Chambers (another of the preprint co-authors) are visiting and I could just ask them to tell me what's in it rather than having to take the trouble to read it myself.

The motivating problem here is distributed sensor networks: one imagines scattering randomly a collection of low-power wireless computing devices over some area, letting them talk to each other, and from that information figuring out the shape of the area they've been spread over. In the oversimplified theoretical model of such networks, two devices can talk to each other if they're within some threshold distance D of each other, and can't talk to each other otherwise, giving a unit disk graph. Once one strips out the topological definitions, Chambers et al propose the following model for reconstructing the shape of the point set from this graph: form a triangle for every three devices that can talk to each other in pairs, and a line segment for every two devices that can talk to each other, take the union of these geometric objects (the “shadow of the Rips complex”), and use that as your approximation to the shape of the points. The nice theorem is that the shadow has the same fundamental group as the Rips complex itself, so that the Rips complex is useful for computing topological information about the shape of the points in a nice coordinate-free way. In some other papers some permutation of these authors also find an efficient algorithm for computing shadows and for testing contractability of cycles on Rips complexes (or equivalently, by their other results, in their shadows).

So that's the good news. The bad news: this all doesn't really work for the sensor network problems. We've made too many assumptions that don't make sense in that application. One of those assumptions, made in the results on algorithms for testing contractability and computing shadows, is that we know the coordinates of the points. But in the sensor network application, the whole difficulty is that we don't know the coordinates — if we did, there are plenty of more direct methods of reconstructing shapes — we want to reconstruct the shape of a point set in a coordinate-free way, and the Rips complex is defined in a nice coordinate-free way but that freedom doesn't extend to the algorithms.

The second bad assumption is that the sensors can talk to each other exactly when they're within D of each other. Really, there's some threshold within which they can talk to each other, some larger threshold beyond which they can't talk to each other, and between those two thresholds they may or may not be able to communicate. To understand this more complex behavior, Chambers et al define a quasi-Rips complex, the flag complex (family of simplices defined from complete subgraphs) of a graph that has edges with the same thresholding behavior. But it turns out (section 4 of the arxiv preprint) that quasi-Rips complexes are a lot less well-behaved than Rips complexes. The fundamental groups of planar regions, and of Rips complexes of planar point sets, are always free, but the fundamental groups of quasi-Rips complexes of planar point sets can be (modulo a free factor) any finitely presented group. The construction involves placing many points in three tightly packed clusters near each of the three corners of an equilateral triangle, allowing the graph from which the quasi-Rips complex is formed to be the complement of an arbitrary tripartite graph.

The upshot of which is that, although interesting as abstract computational topology, it's not yet clear whether the pretty theory can be applied to the practical problems that motivated it. At the least, more work is needed, either smoothing away the topological problems of the quasi-Rips complex or showing that they only arise for unlikely configurations of points, and allowing the algorithms to run even in the absence of coordinates.

### Comments:

None:
2008-01-09T20:43:13Z

Ahh yes, Sensor Networks, the land of dreams. I left the area in part due to a community reluctance to step away from theoretical models, and move toward a, sadly, non-tractable reality. Even the systems side of the community was stuck in a rut using circular emission models when their own measurement studies showed nothing of the like. Still are as far as I know. Protocols that looked great on paper would almost always had fundamental flaws that would kill them in the field.

Never the less, it does sound like interesting work from a topology perspective!

None: A question for the author
2008-01-09T23:54:03Z

Hello, I am a beginning graduate student interested in graph theory. I saw many nice pictures posted by you in Wikipedia: I, myself, am really struggling to find an easy to use graph drawing tool (for Linux) which draws graphs G=(V,E) as the graph theorists (drawing on a blackboard) are used to: just circles or points connected with arrows or lines. I came up with many tools which are either 1) too intricate or 2) understand the shape of "graph" in some other way or 3) look ugly or have an ugly control. So what do scientists use to draw graphs?

11011110: Re: A question for the author
2008-01-10T02:27:57Z

I can't speak for others, but mostly I either use Adobe Illustrator (meaning, I have to place each vertex myself, by hand) or custom software. I understand that graphviz is pretty good as a package for more automatic graph drawing, in which the program decides where to put the vertices and you don't have to tell it how to do so, but I haven't really used it.

chouyu_31: Re: A question for the author
2008-01-10T03:35:28Z

I've used graphviz a few times to generate call graphs, and it works reasonably well for the kind of graph I told it to generate. I tried it with some other graphs, and it produced garbage. It seems hit or miss, depending on the graph.