In graph drawing and geometric graph theory, a Tutte embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average (or barycenter) of its neighbors' positions. Tutte embedding
But I don’t know if this means that such embedding when first we fix any arbitrary outer face (may be convex) can guarantee that each face of is convex.
Edit: Further more: Is Narrate more clearly, is any internal face convex in Tutte ebemdding?
For example, will the following non-convex face $f_1$ appear in Tutte embedding embedding? If it exists, is there a way to make each face convex?
References:
- Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, 13: 743–767,doi:10.1112/plms/s3-13.1.743, MR 0158387.