2
$\begingroup$

Planar graphs are graphs which can be drawn on the plane without edges crossing.

Disk contact graphs are graphs obtained as follows. Place some disks in the plane without overlaps, allowing touching. Create a vertex per disk, and connect vertices by an edge if the corresponding disks touch.

As stated by graph classes, planar graphs and disk contact graphs are equivalent. What I understand from this equivalence is that the two sets contain the same graphs. It is easy to see that any disk contact graph is planar, however I am having trouble understanding how every planar graph is also a disk contact graph.

Is there an intuitive proof? I explicitly ask for an intuitive proof since the link cites a survey paper, which itself cites multiple sources for proofs, although these papers are either impossible to find due to ultimately not being published (or being too old for search engines?) or require some expertise in specific fields which I unfortunately do not have.

$\endgroup$
3
  • 2
    $\begingroup$ This is known as the circle packing theorem. I don't think you'll find a "simple intuitive proof". $\endgroup$ Commented Oct 21, 2021 at 15:08
  • 1
    $\begingroup$ You can check a write up of Asaf Nachmias. $\endgroup$ Commented Oct 21, 2021 at 15:11
  • $\begingroup$ @YuvalFilmus Knowing it is called the circle packing theorem helps a lot already! This article seems to explain some main ideas: triangulate the graph by adding vertices and edges (the corresponding disks can then be removed later), then guess some radii for the disks and check, modify radii and check again etc. After checking Asaf Nachmias' write up very quickly, it seems important to start with the outer vertices/disks also, although I may be mistaken, I'd need to read it more thoroughly. $\endgroup$
    – J. Schmidt
    Commented Oct 22, 2021 at 9:22

1 Answer 1

1
$\begingroup$

This is known as the circle packing theorem, and attributed to Koebe. Asaf Nachmias wrote a short note with a complete proof.

For more on circle packings, check out a survey by Rohde on Oded Schramm's related work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.