Ein Graph ist genau dann planar, wenn er nach dem Satz von Kuratowski keinen Unterteilungsgraphen eines Kuratowski-Graphen enthält. Dieses Kriterium ist bereits seit 1930 bekannt, trotzdem wurde der erste Algorithmus, der einen Graphen auf Planarität in linearer Zeit prüft, erst in den siebziger Jahren des letzten Jahrhunderts formuliert. Moderne Algorithmen dieser Art, genannt Planaritätstests, prüfen nicht nur Graphen auf Planarität, sondern liefern auch eine Einbettung in linearer Zeit, wenn der Graph planar ist und extrahieren darüber hinaus einen Unterteilungsgraphen eines Kuratowski-Graphen, sollte dieser nicht planar sein.

Einer dieser Algorithmen ist der Boyer-Myrvold-Algorithmus, der in der Praxis einer der schnellsten Planaritätstests und im Vergleich zu anderen linearen Planaritätstests einfacher zu implementieren ist. Diese Arbeit ist eine theoretische Untersuchung des Boyer-Myrvold-Algorithmus, einschließlich eines ausführlichen Beweises der linearen Laufzeit sowie dass der Algorithmus einen Graphen korrekt auf Planarität prüft.