Un grafo es un conjunto finito de vértices y aristas, donde las aristas son pares ordenados de vértices. Existen diferentes tipos de grafos, como los grafos regulares, completos, bipartitos, planares, etc. Los grafos planares son aquellos que se pueden dibujar en un plano de tal manera que ninguna arista se interseque con otra.
El Teorema de Kuratowski caracteriza los grafos planares enunciando que un grafo es planar si no contiene al grafo completo K_5 o al grafo bipartito k_3,3.
El estudio de grafos planares está, históricamente hablando, motivado por el problema de colorear un mapa usando la menor cantidad de colores posibles.