ein ebener Graph zusammen mit seinen Ländern.

Eine Färbung einer Landkarte mit k Farben ist eine Abbildung f der Menge aller Länder der Landkarte in die Menge {1, 2,…,k}, der Menge der Farben, so, daß je zwei benachbarte Länder L₁ und L₂ verschiedene Farben erhalten, d. h. f(L₁) ≠ f(L₂).

Zwei Länder müssen also lediglich dann verschiedene Farben erhalten, wenn eine Kante des Graphen ganz zu ihren beiden Rändern gehört, und nicht, wenn die Ränder nur eine Ecke gemeinsam haben. Mit den Färbungen von Landkarten befaßt sich der Vier-Farben-Satz.

Der Begriff der Landkarte läßt sich analog auch für kreuzungsfreie Einbettungen (Einbettung eines Graphen) in orientierbare und nichtorientierbare Flächen beliebigen Geschlechts definieren.