thumb|200px|Przykład grafu planarnego: 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.
Kryterium Kuratowskiego Dwa minimalne grafy, które nie są planarne, to K5 i K3,3. Twierdzenie Kuratowskiego (1930) mówi, że graf skończony jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K5 ani z grafem K3,3.
200px 200px
Twierdzenie Eulera 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 oraz jest grafem spójnym i planarnym, to gdzie – zbiór wierzchołków, – zbiór krawędzi, – zbiór ścian dowolnego rysunku płaskiego grafu
Wnioski ze wzoru Eulera Jeżeli G jest planarny i posiada składowych spójnych, to Jeżeli G jest planarny i to Jeżeli G jest planarny, to wierzchołek o najmniejszym stopniu jest stopnia co najwyżej 5.
Kolorowanie grafu planarnego Twierdzenie o czterech barwach stwierdza iż każdy graf planarny może zostać pokolorowany przy użyciu 4 kolorów.
Zobacz też domki i studnie
Przypisy
Linki zewnętrzne
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). [dostęp 2025-10-12]. Graph, planar , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-04-23].
P Kategoria:Topologiczna teoria grafów