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
    Commented Apr 13, 2021 at 3:30
  • $\begingroup$ You might also be interested in Steinitz's theorem. $\endgroup$
    – Sam Hopkins
    Commented 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$
    – Licheng Zhang
    Commented 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$
    – Licheng Zhang
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .