For any planar graph $G$ with a cut vertex, we can always add a straight edge in some plane drawing of $G$.

129 Views Asked by At

Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments.

Recently, when I was considering the drawing of plane graph, I encountered the following question.

Question Let $G$ be a planar graph with a cut vertex $v$. In some straight-line plane drawing of $G$, are there non-adjacent two vertices, $x$ and $y$ of $G$ such that we can add an edge $xy$ with straight-line segment?

Note: Let $G$ be a connected graph. A vertex $v ∈ G$ is called a cut vertex of $G$, if $G-v$ (Delete $v$ from $G$) results in a disconnected graph.

The answer to the above question is positive from some examples.

Example 1

enter image description here

Example 2 enter image description here

It seems that convex or concave polygon theory will be useful, but I don’t know how to rigorously prove this fact.