Soap bubble graphs

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.

---

Comments: