GRAF PLANNAR

Graf Planar

Adalah Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong (bersilangan) disebut graf planar, jika tidak, maka ia disebut graf tak-planar.

K4 adalah graf planar:

K5 adalah graf tidak planar:

Aplikasi Graf Planar

 Perancangan IC (Integrated Circuit)

Tidak boleh ada kawat-kawat di dalam ICboard yang saling bersilangan -> dapat
menimbulkan interferensi arus listrik -> malfunction

   Perancangan kawat memenuhi prinsip graf planar

Teorema Kuratoswki

Teorema Kuratowski. Graf G bersifat planar jika dan hanya jika ia tidak mengandung upagraf yang isomorfik dengan salah satu graf Kuratowski atau homeomorfik (homeomorphic) dengan salah satu dari keduanya.

Berguna untuk menentukan dengan tegas keplanaran suat graf. 

a)     Graf Kuratowski pertama (K5)     

b)     Graf Kuratowski kedua (K3, 3)        

c)      Graf yang isomorfik dengan graf Kuratowski kedua 

Sifat graf Kuratowski adalah:

1.      Kedua graf Kuratowski adalah graf teratur.

2.      Kedua graf Kuratowski adalah graf tidak-planar

3.      Penghapusan sisi atau simpul dari graf Kuratowski menyebabkannya menjadi graf planar.

4.    Graf Kuratowski pertama adalah graf tidak-planar dengan jumlah simpul minimum, dan graf Kuratowski kedua adalah graf tidak-planar dengan jumlah sisi minimum.