Plokščiasis grafas
Plokščiasis grafas – toks grafas, kurį galima pavaizduoti plokštumoje taip, kad nė viena briauna nesikirstų. Kitaip dar vadinamas planariniu grafu. Neplokščiojo grafo pavyzdys paveikslėlyje kairėje. Šio grafo neįmanoma perpiešti plokštumoje taip, kad briaunos nesikirstų. Iš tiesų tai vienas iš dviejų mažiausių neplokščiųjų grafų. Lenkų matematiko Kazimiero Kuratovskio suformuluota teorema apie plokščiuosius grafus (Kuratovskio teorema) teiga, kad: Baigtinis grafas yra plokščiasis tada ir tik tada, jei neturi pografio, kuris būtų homeomorfinis grafui K5 (pilnasis 5 viršūnių grafas) arba K3,3. Deja, naudojantis Kuratovskio teorema negalima greitai nustatyti ar grafas plokščiasis. Tačiau egzistuoja greiti O(n) sudėtingumo algoritmai, sprendžiantys šią problemą (n – viršūnių skaičius).