adding edges to a planar graph

Question

Let G be a finite, planar, disconnected graph with two components.

Is it always possible to add an edge to the graph to make it connected and still planar?

Answer 1

The answer is yes.

---

Rigorous proofs regarding planarity of a graph usually use non-trivial theorems such as Jordan curve theorem, and theorems about embedding, which I will avoid, and therefore will give intuition, and not a full answer.

Constructive Proof

Denote the two disconnect planar graphs by $G,H$. Since they are both planar, one could embed them on the plane $\mathbb R^2$ with straight edges (and not just curves) This is equivalent to stating:

1. $G$ could be embedded in $\{(x,y)\in\mathbb R^2|x>0\}$ with straight edges.
2. $H$ could be embedded in $\{(x,y)\in\mathbb R^2|x<0\}$ with straight edges.

Now Denote by $F_1,F_2$ thier outer faces, with bouderies $A\subset V(G),B\subset V(H)$.

Proposition one could connect by an edge the two faces.

Proof:

Pick $v\in G$ whose $x$ coordinate is minimal (maybe not unique). Pick $u\in H$ whose $x$ coordinate is maximal (maybe not unique). Connect them by a straight edge.
By the choice of $v,u$, and the fact all previous edges were segments, we can conclude the new graph is also planar, by the new obtained embedded.

Existence Proof

One a second thought, I think it might be easier to use Kuratowski's theorem and Wagner theorem and prooving:

By adding one edge between two disconnected graphs $G,H$, you could not form $K_5, K_{3,3}$ subdivision or minor.

A proof sketch would be: $$\forall v\in G\ \ \deg_H(v)=0\\ \forall u\in H\ \ \deg_G(v)=0\\ $$

Answer 2

Let $C,C'$ the two connected components of $G$. By Fáry's theorem, there is an embedding into the plane that maps edges to line segments. We will identify $G$ with its image under such an embedding. WLOG, the convex hull $H$ of $C$ and the convex hull $H'$ of $C'$ have empty intersection (just translate $C'$ out of $H$). Let's call $d$ the Euclidean distance.

Both $H$ and $H'$ are polygons whose edges are edges of $C$ and $C'$ respectively. Take vertices $v, v'$ in the boundaries of $H,H'$ respectively such that $d(v, v')$ is minimal.

Clearly, if you add the edge $(v,v')$ to your graph, it is connected and still planar.