Proving a graph is planar - mutually tangent circles in a plane

Question

Let $C_1,\dots ,C_n$ be circles in the plane with pairwise disjoint interiors. Define the tangency graph to have $n$ vertices such that vertices are adjacent if the corresponding circles are tangent to each other. Prove this graph is planar.

It looks like I have to prove there can't be minor $K_5$'s or $K_{3,3}$'s. For $K_5$, I thought to prove there's no $K_4$ anywhere. Thing is, I don't even know how to rigorously prove we can't have four pairwise tangent circles in the plane. This doesn't even cover minors and I have no idea how to tackle $K_{3,3}$'s... How to solve this problem? How should such problems be approached?

Answer 1

As Mariuslp said in the comments, you can explicitly construct a planar embedding of the tangency graph. Given your collection of circles $C_1, \dotsc, C_n$ that are pairwise disjoint in the plane, construct the graph by taking a vertex at the center of each circle and connecting vertices by an edge if the two circles are tangent. Note that each edge will pass through the point of tangency and that each edge is completely contained in the interior of the two tangent circles. I claim that this graph is planar.

For the sake of finding a contradiction, if this graph weren't planar then there would be a pair of intersecting edges $(a,b)$ and $(c,d)$ which are between the vertices $a,b$ and $c,d$ respectively, which are at the centers of the circles $C_a$, $C_b$, $C_c$, and $C_d$ respectively. Without loss of generality, let $t$ be the point of tangency of $C_a$ and $C_b$ and suppose that $t$ does not lie on $(c,d)$. Then $t$ must lie on one side $(c,d)$^[1], so one of the circles $C_c$ or $C_d$ intersects $(c,d)$, contradicting that the interior the circles are disjoint. The other case is that the points of tangency of the two pairs of circles are the same point and lie at the intersection of $(a,b)$ and $(c,d)$. But in this specific case we can clearly see that some of the must circles intersect. This contradicts the possibility of the graph being non-planar.

---

[1] To be more precise $t$ must lie on one side of the line containing $(c,d)$.

Answer 2

It's obvious: Take the centers $v_i$ $(1\leq i\leq n)$ of the circles as vertices and connect two vertices by a straight segment if the corresponding circles are tangent to each other.

Or have I missed something?