A barycentric mapping of a planar graph is a plane
embedding in which every internal vertex is the average
of its neighbours. A celebrated result of Tutte's
is that if a planar graph is nodally 3-connected then
such a mapping is an embedding. Floater generalised
this result to convex combination mappings in which every
internal vertex is a proper weighted average of its neighbours.
He also generalised the result to all triangulated
This has applications in numerical analysis (grid generation), and in computer graphics (image morphing, surface triangulations, texture mapping).
Also, White showed that every chord-free triangulated planar graph is nodally 3-connected.
We show that (i) a nontrivial plane embedded graph is nodally 3-connected if and only if every face boundary is a simple cycle and the intersection of every two faces is connected; (ii) every convex combination mapping of a plane embedded graph is an embedding if and only if (a) every face boundary is a simple cycle, (b) the intersection of every two faces is connected, and (c) there are no so-called inverted subgraphs; (iii) equivalently, the graph admits a convex embedding, as investgated by Stein; and (iv) any two such embeddings (with the same orientation) are isotopic.
These results were presented in the fourth MFCSIT conference, Cork, Ireland, August 2006. The paper is an improved version of TCDMATH--05--10 (on barycentric embeddings), though the latter paper includes some results not used in this paper.