Ein ebener Graph ist ein Graph, dessen Ecken Punkte in der Ebene sind, und alle Kanten kreuzungsfreie Verbindungslinien in dieser Ebene zwischen den entsprechenden Punkten sind. Ebene Graphen können als Landkarte aufgefasst werden, die Eulersche Polyederformel liefert einen Zusammenhang zwischen den Anzahlen der Ecken, Kanten und Länder. Außerdem lässt sich einem ebenen Graphen ein dualer Graph zuordnen, beim dem die Rollen der Ecken und Länder vertauscht werden. Aus verschiedenen Gründen ist es interessant zu wissen, ob ein gegebener Graph als ebener Graph dargestellt werden kann. Solche Graphen heißen planar. Sie können durch den Satz von Kuratowski charakterisiert werden.