Graf Planar (Planar Graph) dan Graf Bidang (Plane Graph) 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: Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph). Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang . Aplikasi Graf Planar Persoalan utilitas (utility problem) a) Graf persoalan utilitas (K3,3), (b) graf persoalan utilitas bukan graf planar. P erancangan IC (Integrated Circuit) Tidak boleh ada kawat-kawat di dalam ICboard yang salin bersilangan dapat menimbulkan interferensi arus listrik malfunction Perancangan kawat memenuhi prinsip graf planar. Latihan 1. Misalkan graf...
