Graf planarny

Graf planarny – graf, który można narysować na płaszczyźnie (i każdej powierzchni genusu 0) tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim^[1].

Dwa minimalne grafy, które nie są planarne, to K₅ i K_3,3. Twierdzenie Kuratowskiego (1930) mówi, że graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K₅ ani z grafem K_3,3.

Dowolny rysunek płaski grafu planarnego wyznacza spójne obszary płaszczyzny zwane ścianami. Dokładnie jeden z tych obszarów, zwany ścianą zewnętrzną, jest nieograniczony.

Zgodnie z wzorem Eulera, jeżeli ${\displaystyle |V|\geqslant 3}$ oraz ${\displaystyle G}$ jest grafem spójnym i planarnym, to ${\displaystyle |V|+|S|-|E|=2,}$ gdzie ${\displaystyle V}$ – zbiór wierzchołków, ${\displaystyle E}$ – zbiór krawędzi, ${\displaystyle S}$ – zbiór ścian dowolnego rysunku płaskiego grafu ${\displaystyle G.}$

• Jeżeli G jest planarny i posiada ${\displaystyle k}$ składowych spójnych, to ${\displaystyle |V|+|S|-|E|=k+1.}$
• Jeżeli G jest planarny i ${\displaystyle |V|\geqslant 3,}$ to ${\displaystyle |E|\leqslant 3\cdot |V|-6.}$
• Jeżeli G jest planarny, to wierzchołek o najmniejszym stopniu jest stopnia co najwyżej 5.

Twierdzenie o czterech barwach stwierdza iż każdy graf planarny może zostać pokolorowany przy użyciu 4 kolorów.

• domki i studnie

• MarcinM. Kotowski MarcinM., MichałM. Kotowski MichałM., Kafelkowanie prostokątów i grafy planarne, „Delta”, październik 2014, ISSN 0137-3005 [dostęp 2025-06-03] .
• Grafy planarne, Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej (MiNI PW), kanał „Archipelag Matematyki” na YouTube, 16 sierpnia 2017 [dostęp 2024-09-04].
• Oskar Skibski, Grafy Planarne [w:] Matematyka Dyskretna, kanał autorski na YouTube, 3 maja 2020 [dostęp 2026-01-17] – nagranie w ramach kursu, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIM UW).
• Eric W.E.W. Weisstein Eric W.E.W., Planar Graph, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2025-10-12].
• Graph, planar (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-04-23].