Abstract:
Graf planar adalah graf yang dapat digambarkan di bidang datar(seperti kertas) tanpa
terdapat sisi yang saling berpotongan. Suatu graf planar jika diacak posisi simpulnya
akan menjadi terlihat seperti tidak planar lagi. Pentingnya penempatan simpul ini
menjadi ide dasar untuk membangun sebuah permainan.
Permainan yang dibuat bernama planarity. Dalam permainan ini, pemain diberikan
sebuah graf planar yang diacak posisi simpulnya. Dengan demikian graf tersebut
menjadi terlihat tidak planar karena terdapat sisi-sisi yang saling berpotongan. Pemain
ditugaskan untuk membuat graf tersebut menjadi terlihat planar kembali(tidak terdapat
lagi sisi-sisi yang saling berpotongan), dengan cara memindahkan posisi simpulsimpulnya.
Graf planar dibangun menggunakan randomized incremental algorithm.
Algoritma ini bertujuan untuk membangun delaunay triangulation dari himpunan titik.
Sifat-sifat dari delaunay triangulation memenuhi sifat dari graf planar. Dengan
demikian, graf planar didapat dengan membuat delaunay triangulation dari himpunan
titik.
Permainan telah dibangun diuji ke beberapa pengguna. Randomized incremental
algorithm berhasil membangun graf planar secara acak yang layak dimainkan. Pengujian
dilakukan dengan mengukur berapa lama waktu yang dibutuhkan pemain dalam
menyelesaikan permainan. Pada setiap kenaikan jumlah vertex, standar deviasi yang
didapat semakin bertambah besar. Dengan demikian tidak dapat diukur rata-rata kecepatan
pemain dalam menyelesaikan permainan.
