planaritást

A planaritás (vagy planaritás) a gráfelméletben annak a tulajdonsága, hogy egy adott gráf síkba beábrázolható-e úgy, hogy az élek kereszteződés nélkül találkozzanak. Egy síkba ábrázolt gráfot síkba rajzolt vagy plane gráfnak is szokták nevezni. A planáris gráfokat olyan megjelenítésben lehet szemléltetni, ahol az élek csak a végpontjaiknál találkoznak.

A planaritás kulcsfontosságú elméleti eredménye a Kuratowski-tétel: egy véges gráf síkba beábrázolható, ha és csak ha nem tartalmaz kuratowskii szubdivíziót (vagyis elágazását) a K5- vagy a K3,3 gráfokból. Más szavakkal, a K5 vagy a K3,3 kisebb részgráfjaként vagy ezek elágazásaiként előforduló szerkezetek jelenléte megakadályozza a síkba való ábrázolást. A Wagner-tétel is közvetett kapcsolatban áll a területtel, hiszen a planaritás minorekkel kapcsolatos.

A síkban való beábrázolásokat Euler-képlet írja le: ha a gráf kapcsolt, akkor V - E + F = 2, ahol V a csúcsok, E az élek, F pedig a sík által borított égbolton lévő arányokat jelenti. Ennek következményei vannak a síkba rendezhetőségre vonatkozó korlátokra, például küszöbértékek adhatók meg a kapcsolt planáris gráfokra vonatkozóan (például az E ≤ 3V - 6 feltétel adott kivételekkel).

Gyakorlati jelentősége a planaritásnak a gráfábrázolások, hálózattervezés és áramkör-tervezés területén van, ahol a kereszteződések minimalizálása olvashatóbb és hatékonyabb vizualizációt és kivitelezést tesz lehetővé. További kutatási területek közé tartoznak a planaritás teszteléseinek hatékony algoritmusai és a síkba fogalmazható grafok speciális osztályai.