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 verteks).
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.
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.
