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

Improve this question
$\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
    Commented 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$
    – Licheng Zhang
    Commented Sep 4, 2021 at 0:46

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

You must log in to answer this question.

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