1
$\begingroup$

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: : 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?

enter image description here

References:

Improve this question
$\endgroup$
8
  • $\begingroup$ $w$ will be placed midway along the line connecting $e$ and $z$, so the face will never appear as you have drawn it. $\endgroup$
    – Gordon Royle
    Apr 13, 2021 at 3:30
  • $\begingroup$ You might also be interested in Steinitz's theorem. $\endgroup$
    – Sam Hopkins
    Apr 13, 2021 at 3:32
  • $\begingroup$ @GordonRoyle Thank you very much for your answers. I already understand what you mean, for this example, there really is no such drawing in Tutte embemdding. This is just an example of mine. Maybe not good. I don’t know if any non-convex face can also be excluded for the general situation. $\endgroup$
    – L.C. Zhang
    Apr 13, 2021 at 3:36
  • $\begingroup$ @SamHopkins Steinitz's theorem seems to only say that there is a correspondence between a 3-connected plane graph and a convex polyhedron, but I am not sure that given an any convex(may be not) external face, it can guarantee that there is a plane straight-line drawing where anyinternal face is all convex. Maybe I don't understand it well. $\endgroup$
    – L.C. Zhang
    Apr 13, 2021 at 3:46
  • 1
    $\begingroup$ Tutte's method works with any face on the outside drawn as any convex polygon. It doesn't matter which face you choose. But this assumes 3-connectivity. Without 3-connectivity there might not be any Tutte drawing at all. For a simple example, suppose there is a cut-vertex -- then some face has a vertex appearing twice so it is impossible to draw it convex. $\endgroup$
    – Brendan McKay
    Apr 13, 2021 at 4:27

1 Answer 1

Reset to default
3
$\begingroup$

I think that for a 3-connected planar graph, any Tutte embedding has all faces represented as convex polygons.

In the linked paper, Tutte says (page 759, before (9.3)) that a barycentric mapping is a convex representation as defined in [Convex Representations of Graphs, Proc. London Math Soc. 1960].

In this paper, he defines a convex representation to be (paraphrasing) a planar straight-line drawing that separates the plane into a finite number of regions, “each of which is either the interior or exterior of a convex polygon”.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.