planiteit

Planiteit, in de grafentheorie vaak planarity genoemd, is de eigenschap van een graf om getekend te worden op het vlak zonder kruisingen tussen randen (uitgezonderd kruisingen bij gemeenschappelijke knopen). Een graf dat deze eigenschap bezit, heet planar. Als een graf niet planar is, bestaat er geen kruisingvrije tekening.

Bij een verbonden planar graf geldt Euler’s formule V − E + F = 2, met V het aantal knopen, E het aantal randen en F het aantal vlakken (faces). Een belangrijke gevolgtrekking is dat voor een planar graf met V ≥ 3 E ≤ 3V − 6. Voor outerplanar grafen gelden strengere grenzen: E ≤ 2V − 3.

Kuratowski’s stelling: een eindige graf is planar als en slechts als hij geen subgraf bevat die homeomorf is aan K5 of K3,3. Een equivalente karakterisering gebruikt minoren (Wagner’s theorema): planariteit houdt op tegen deze twee onvoltooide minoren. Planariteit kan ook worden gezien via embeddings op de bol: elke planar graf kan zonder kruisingen op een bol getekend worden, en omgekeerd levert een bolomvattende projectie een vlakke tekening op.

Voorbeelden en niet-voorbeelden: bomen en cirkelgrafen zijn planar; het volledige graf K5 en het bipartiete graf K3,3 zijn niet planar.

Toepassingen en algoritmen: planarity testing is fundamenteel in grafische visualisatie, elektronische schakelingen en geografische informatiesystemen. Er bestaan algoritmen voor planarity-testing in lineaire tijd, zoals die van Hopcroft–Tarjan en Demoucron–Malgrange–Pertuiset, die ook helpen bij het vinden van een planar embedding. Planariteit is bovendien relevant voor het concept van outerplanar grafen en voor import- en visualisatietechnieken.