1
$\begingroup$

When I looked up the definition of convex drawing of planar graph, my confusion mainly focused on the outer face.

The following definition of convex drawing is from Wikipedia.

In graph drawing, a convex drawing of a planar graph is a drawing that represents the vertices of the graph as points in the Euclidean plane and the edges as straight line segments, in such a way that all of the faces of the drawing (including the outer face) have a convex boundary.

It gives two examples

enter image description here

Surprisingly, the outer face is not convex in the second example. enter image description here

I 'd like to ask what is the convex boundary of outer face here? The outer face doesn't seem to be convex and I feel that the unbounded face is the complement of a convex set.

So I'm confused by the definition of convex drawing where boundary of the outer face is also convex. I don't know where I got it wrong.

I searched the Mathemaics Stack for a similar puzzle below. There seems to be no consensus. https://math.stackexchange.com/questions/940693/convex-planar-graphs

$\endgroup$
2
  • 1
    $\begingroup$ I believe the operative phrase in the definition is “have a convex boundary”. The definition does not say that the faces must be convex sets, but rather that the boundary of each face must be convex (i.e., must bound a convex region in its interior). $\endgroup$
    – dwilburne
    Sep 4, 2021 at 0:41
  • $\begingroup$ @dwilburne I see. Thank you! I confused the polygons formed by the edges of the outer face with the outer face. $\endgroup$
    – L.C. Zhang
    Sep 4, 2021 at 0:46

1 Answer 1

2
$\begingroup$

Wikipedia does not state that the outerface is convex, but rather that it has a convex boundary. I assume this means that the set consisting of all points inside the boundary is convex. So for example, the outerface has a convex boundary in your two examples. Also, with this definition, it is true that every $3$-connected planar graph has a convex drawing (since it is the $1$-skeleton of a $3$-polytope).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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