Planarity testing algorithms in graph theory

Bir çizgenin düzlemsel olup olmadığını belirlemek ve düzlemsel bir çizgeyi gömmek, çizge kuramı ve çizge çizimleri alanlarının en ilgi çekici ve büyüleyici algoritmik sorunlarından biridir. Bu tezde, basit ancak verimli algoritmalar yardımıyla bu tür problemler çözmenin basit yöntemleri ele alınmaktadır. Tezin 4. bölümünde, literatürde yer alan ve dümleselliği test etmek için kullanılan algoritmaların neredeyse tamamı listelenerek konuyla ilgili kısa ancak kapsamlı bir tarihsel süreçte sunulmakadır. Bu yüksek lisans tezinde iki doğrusal-zaman algoritması ve bir kuadratik-zaman algoritması tartışılmıştır. Sunulan algoritmalar bir çizgenin düzlemselliğini manuel olarak test ederken hangi algoritmanın daha kullanışlı olduğunu görmek için her algoritma iki örnek üzerinde de uygulanmıştır. Elde edilen bulgulara göre, Boyer-Myrvold algoritması, az sayıda köşeye sahip belirli bir çizgenin düzlemselliğini manuel olarak test etmek için en hızlı algoritmadır. Bununla birlikte, LEDA'da (Verimli Veri Tipleri ve Algoritmalar Kütüphanesi) çok sayıda köşe noktası olan çizgelerde yapılan testlere dayanarak, Sol-Sağ düzlemsellik algoritmasi en hızlı algoritmadır.