Last week I was in Prague as one of four invited speakers at the EuroGIGA Midterm Conference; EuroGIGA is a big multi-investigator European research project on graphs, geometry, and algorithms.
My talk there was entitled "Möbius transformations, power diagrams, Lombardi drawings, and soap bubbles", and it announced the results of two papers that I've recently uploaded to the arXiv: "Planar Lombardi drawings for subcubic graphs" (arXiv:1206.6142) and "The graphs of planar soap bubbles" (arXiv:1207.3761).
I think it's easier to explain what I'm doing in the soap bubble one, so let's start with that. The following picture could not possibly be a (two-dimensional) soap bubble, but why not?
One reason is that it has vertices where a straight edge and two curved edges of different curvatures meet, which can't happen in soap bubbles, but maybe I've just drawn it inaccurately. Is there some other drawing with the same topological connectivity as this one that does form a valid soap bubble? You might say that the answer is no, because soap bubbles form minimal surfaces and the edges in the middle are not minimal because they can be contracted. However, to me this is an unsatisfactory answer. "Things that form minimal surfaces" is fine as a mathematical definition but not so good as a definition of soap bubbles, which are after all physical objects that have no notion of minimality. The fact that soap bubbles are minimal isn't defining for them, it's an emergent property coming from the way the more fundamental physical forces of surface tension and air pressure act when in equilibrium. But it is true that the drawing above does not have the topological connectivity of a soap bubble, and now I can prove it.
There are two basic ingredients in both papers. The first is the circle packing theorem of Koebe, Andreev, and Thurston, which states that any maximal planar graph can be represented as a collection of non-crossing circles in the plane such that two graph vertices are adjacent if and only if the corresponding two circles are tangent. The second is a new type of power diagram that can be defined by forming a three-dimensional hyperbolic Voronoi diagram of halfspaces and then restricting it to the plane at infinity. If you apply the new power diagram to a circle packing, you get something like the figure below, which shows a soap bubble with the topological connectivity of the Frucht graph overlaid on the circle packing from which it was constructed.
This new power diagram of a circle packing turns out to always be a Lombardi drawing, and also to always obey the physical laws describing soap bubbles: Plateau's laws and the Young–Laplace equation. For 2d soap bubbles, Plateau's laws are essentially the same as the requirements of Lombardi drawing, that the edges be circular arcs that meet at equal angles at the vertices, but the Young–Laplace equation is an additional requirement on the curvatures of the arcs. Not all Lombardi drawings obey the Young–Laplace equation; the figure I started with, with the non-minimal edges, gives an example of a Lombardi drawing that does not obey it.
The Lombardi drawing paper uses this construction to prove that all planar graphs of degree at most three and some of degree four have planar Lombardi drawings; it also provides an example of another degree-four graph that has no planar Lombardi drawing. The soap bubble paper characterizes the graphs of planar soap bubbles as being exactly the bridgeless 3-regular planar graphs, using the same construction for one side of the characterization and using the Möbius invariance of the Young–Laplace equation to prove the other side, the fact that soap bubbles cannot have any bridge edges.
Very nice results! The link to your talk is broken though. A few questions:
C. Moukarzel showed that soap bubbles in 2D are what he called sectional multiplicative Voronoi partitions (that is for any 2D soap bubble, you can find a set of sites and weights in 3D such that if you form the multiplicative Voronoi diagram from them, the soap bubble is a particular 2D slice of it). Is this related at all to the power diagram that you defined?
Does the result extend in an obvious way to foams on tori (or more generally other surfaces)? Gareth McCaughan showed that there are restrictions on the moduli of tori that admit circle-packings, so perhaps what your results imply is simply that any bridgeless 3-regular graph on a torus can be realized as soap bubble on some torus that you can construct? What would be needed to show that such graphs can be realized on any torus?
It is sort of related, actually. My construction uses something that is sort of a multiplicatively weighted power diagram (i.e. it differs from the standard Voronoi diagram in two ways, one of which is weighted like a power diagram and the other is weighted like a multiplicative Voronoi diagram). And power diagrams are sections of 3d Voronoi diagrams.
To realize this on a flat torus (i.e. a repeating pattern in the plane with translational symmetry) all you would need is to be able to construct circle packings for the dual graph of the desired bubble. But the parts of my paper that extend the bubble construction to 3-connected graphs to 2-connected graphs, and that prove that bridges are impossible, both depend on Möbius transformations, which don't make as much sense in the torus case.
Thanks for the reply! I'll have to think about these things some more.
The link to your talk is still broken.
Oops, sorry about that, I fixed the link now.