Un graphe est dit planaire si l'on peut le dessiner sur une feuille de papier (ou sur une pastille de silicium !) sans que ses arêtes ne se croisent. Par exemple, le graphe complet sur quatre sommets (tout sommet est relié aux trois autres) est planaire. Par contre, les graphes K5 et K3,3 ne le sont pas. De plus, Kuratowski a montré en 1930 qu'un graphe est non-planaire si et seulement si il "contient" (dans un sens à préciser) au moins une copie de l'un de ces deux graphes. Pour en savoir plus...