I have a new preprint out, “Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs”, with Alvin Chiu and Mike Goodrich, arXiv:2307.10527, to appear at Graph Drawing. (I already wrote about my other Graph Drawing accept last January.) It’s an experimental rather than theoretical paper, the main idea of which is to try different weights of springs in the Tutte spring embedding of planar graphs, in order to try to avoid the exponentially-close vertex spacing that typically results from this embedding.

It was known from past work of Chrobak, Goodrich, and Tamassia (SoCG 1996, doi:10.1145/237218.237401) that, for graphs with a triangular outer face, you could construct a Tutte embedding with vertices that have approximately evenly-spaced \(x\)-coordinates, and in an appendix we extend this to exactly evenly-spaced \(x\)-coordinates, without the restriction on the outer face. This prevents vertices from being exponentially close: in an \(n\)-vertex graph, the ratio between the minimum and maximum distance is \(O(n)\), as good as you could hope for. But doing this can still sometimes produce drawings where some parts of the graph are squished very close to a line, making them illegible. It’s this squishing effect that our experiments are intended to circumvent.

Instead of repeating its material in this post, I wanted to highlight a correction to some past literature related to this method, buried in a footnote of the new preprint. It involves the problem of finding the shapes of convex polyhedra given only a combinatorial description of the polyhedra, their graphs. The graph of vertices and edges of any convex polyhedron is a planar 3-vertex-connected graph. Steinitz’s theorem says that this is a complete description: every planar 3-vertex-connected graph can be realized as a convex polyhedron. One way to do this involves Tutte embeddings: for certain Tutte embeddings (including the ones with a triangular outer face) you can “lift” the embedding by adding a third \(z\)-coordinate to the \(x\)- and \(y\)-coordinates that you already have, turning it into a convex polyhedron.

Chrobak, Goodrich, and Tamassia used this idea to produce realizations of graphs as convex polyhedra with the property that the polyhedron vertices are well-separated from each other, with the same \(O(n)\) ratio between minimum and maximum distance. Only, they were a little sloppy in the wording of their result, stating it as a theorem for all polyhedral graphs, when really their method only works for polyhedra that have a triangular face.

The existence of a polyhedral realization with this vertex separation property, claimed but not fully proven by Chrobak et al., was finally resolved by André Schulz in his paper “Drawing 3-polytopes with good vertex resolution” (JGAA 2011, doi:10.7155/jgaa.00216). Schulz noticed the incorrectly-omitted assumption of a triangular face in the work of Chrobak et al., and described how to modify the Tutte embedding weights to make a similar method work when there is no triangular face.

The “squishing” problem remains in this three-dimensional version of the problem, though. One way to address it is to ask about the area of the faces of a Tutte embedding or polyhedral realization, instead of the separation of its vertices. Does every 3-connected planar graph have a weighted Tutte embedding in which every face has area that is at least a polynomial fraction of the area of the whole drawing? Does it have a polyhedral realization in which every face has area that is at least a polynomial fraction of the surface area of the polyhedron? There are methods known for finding planar drawings in which all faces have large area (for instance by drawing the graph with all vertices placed in a grid) but, unlike for Tutte embeddings, I don’t think any of these are known to lift to polyhedra.

(Discuss on Mastodon)