Concise yet Rigorous Proof: How to Modify It?

69 Views Asked by At

The following proposition is standard.

Proposition 1. Let $G$ be a graph with a planar drawing $D$ and at least three vertices. Then, $D$ can be extended to a multi planar drawing $D^*$ by adding some uncrossed edges such that $D^*$ is triangulated.

I give a brief proof (just briefly mention it), but I always feel like it lacks accuracy.

Proof: It is always possible to triangulate $D$ by repeatedly adding uncrossed edges to face with degree more than three.

I feel that the phrase adding uncrossed edges to the face is not good. I mean if a face $f$ with degree more than three, then there are two non-consecutive vertices on the boundary of $f$, then we can add the edge between the two non-consecutive vertices and draw the edge inside the face. Then we can triangulate $D$ by repeating the above process.

But the passage above appears to be verbose. I would like to provide a concise yet rigorous proof (actually, just briefly mention it). How should I modify it?

Note that the degree of a face is the length of its boundary.


In fact, I'm also considering the case of a 1-planar graph (A graph is called 1-planar if it can be drawn in the plane so that each its edge is crossed by at most one other edge).

Similarly I take into account the following statement:

Proposition 2. Let $G$ be a graph with a 1-planar drawing $D$ and at least three vertices. Then, $D$ can be extended to a multi 1-planar drawing $D^*$ by adding some edges such that $D^*$ is triangulated.

Before I give its proof, I give this lemma.

Lemma 1. Let $G$ be a $1$-planar graph with a $1$-planar drawing $D$. Let $f$ be a $k$-region of $D$ where $k\ge 4$. Then there are at least two non-consecutive vertices on the boundary of $f$.

Similarly, I also wish to provide a concise yet rigorous proof. Now I can say: By Lemma 1, , it is always possible to triangulate $D$ by repeatedly adding uncrossed edges to region with degree more than three. Likewise, I also find it lacking in rigor.