Sebuah graf G = (V,E) disebut graf planar apabila graf tersebut dapat digambarkan dalam sebuah bidang datar tanpa ada sisi/edge yang saling berpotongan (kecuali sisi sisi berpotongan pada sebuah vertex.
Contoh Graf Planar
Contoh Graf Non Planar
Teorema Kuratowski :
“ Graf G bersifat planar jika dan hanya jika ia tidak mengandung subgraf yang sama dengan salah satu graf kuratowski atau homomorfis dengan salah satunya “
Sifat GRAF Kuratowski adalah :
1. Kedua graf kuratowski adalah graf teratur
2. Kedua graf kuratowski adalah graf non-planar
3. Penghapusan sisi atau simpul dari graf kuratowski menyebabkan menjadi graf planar
4. K5 adalah graf non-planar dengan jumlah simpul minimum, K3,3 adalah graf non-planar dengan jumlah sisi minimum.