Planar graf

Ein planar graf er i grafteori ein graf som kan teiknast i planet utan at nokre av kantane skjer kvarandre. Ein ikkje-planar graf kan ikkje teiknast på ein sånn måte. Ein plan graf er ein planar graf som er teikna i planet. Ein kan definere ein plan graf som ein planar graf med ei avbilding frå kvart hjørne til eit punkt i det todimesjonale rommet, og frå kvar kant til ei plan kurve, slik at endepunkta til kvar kurve samsvarer med posisjonane til endehjørna, og alle kurvene er disjunkte bortsett frå i endepunkta.

Kuratowskis sats

K₅

K_3,3

Den polske matematikaren Kazimierz Kuratowski gav ei karakterisering av planare grafar, nå kjend som Kuratowskis sats:

Ein endeleg graf er planar viss og berre viss den ikkje inneheld ein undergraf som er ein subdivisjon av K₅ (den komplette grafen med fem hjørne) eller K_3,3 (den komplette bipartite grafen med tre hjørne i kvar del).

En subdivisjon av ein graf får ein ved å leggje til eit eller fleire hjørne i ein kant, (til dømes ved å endre kanten •——• til •—•—•) og gjenta dette null eller fleire gonger.

Eigenskapar

Viss ein teiknar ein planar graf i planet, rammar han inn eitt eller fleire område. Viss n er talet på hjørne, m er talet på kantar og f er talet på område, seier Eulers formel at n - m + f = 2. Av dette kan ein vise at m ≤ 3n - 6 for alle planare grafar.

Firefargersatsen seier at hjørna i ein planar graf alltid kan verte farga med fire farger sånn at to naboar alltid har ulike farger.