Nodally 3-connected planar graphs and barycentric embeddings

This paper is largely supplanted by improved results on convex combination mappings in TCDMATH--06--16, though it includes some results not needed in the latter paper.

An interesting question about planar graphs is whether they admit plane embeddings in which every bounded face is convex. Stein gave as a necessary and sufficient condition that every face boundary be a simple cycle and every two bounded faces meet in a connected set, with an extra condition about the number of vertices on the outer face. Tutte gave a similar characterisation, and later showed that every nodally 3-connected planar graph admits a barycentric embedding. Floater generalised this to convex combination mappings of triangulated graphs. White showed that a chord-free triangulated graph is nodally 3-connected and showed that Tutte's result applies to all triangulated graphs. We extend Tutte's results beyond the class of triangulated graphs.

We show that a biconnected plane-embedded graph is nodally 3-connected if and only if the intersection of any two faces, bounded or otherwise, is connected.
If a plane embedded graph admits a convex embedding, then every face boundary is a simple cycle, the intersection of every two faces is connected, and there are no inverted subgraphs (as defined in the paper). Such graphs we call admissible. The idea of admissible embedded graph is more useful than Stein's criterion and simpler than Tutte's. We show that every admissible plane embedded graph admits a barycentric embedding. It follows immediately that a plane embedded graph has a convex embedding if and only if every barycentric map is an embedding.
Finally we show that when a plane embedded graph admits a barycentric embedding, the two embeddings are isotopic.