Membangun permainan PLANARITY menggunakan randomized incremental algorithm

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.