Pohon Rentang Geometrik Bidang Yang Kompatibel

Compatible Plane Grometric Spanning Tree

Dua graf geometrik bidang pada himpunan titik 𝑆 dikatakan kompatibel jika gabungan kedua graf 

tersebut juga merupakan sebuah graf geometrik bidang pada 𝑆 . Diberikan sebuah pohon perentang

geometrik bidang 𝑇 pada himpunan 𝑆. Fokus permasalahan dalam artikel ini adalah mencari sebuah

pohon perentang geometrik bidang 𝑇1 pada 𝑆 sedemikian hingga 𝑇1 kompatibel-𝑇 dan banyak sisi 

𝑇1 dan 𝑇 yang bersekutu minimum. Minimum banyaknya sisi 𝑇 dan 𝑇1 yang bersekutu dilambangkan

dengan 𝑑(𝑇). Secara umum menentukan nilai 𝑑(𝑇) merupakan masalah menarik tetapi sulit, karena 𝑑(𝑇)

tergantung pada dua hal yaitu kelas pohon 𝑇 itu sendiri, dan letak titik-titik 𝑆 pada bidang datar. Jika 

𝑇 pohon khusus seperti bintang diperoleh 𝑑(𝑇) = 1. Sebuah triangulasi  dari pohon 𝑇 adalah sebuah

graf diperoleh dari 𝑇 dengan menambahkan sebanyak mungkin sisi-sisi baru, namakan sisi-sisi merah, ke 

𝑇 sedemikian hingga graf baru tetap geometrik bidang dengan setiap internal muka berbentuk segitiga. 

Pada umumnya, triangulasi  dari 𝑇 tidak tunggal, minimum banyaknya komponen graf  − 𝑇 , 

dilambangkan dengan 𝐶(𝑇). Dibuktikan bahwa untuk pohon geometrik bidang 𝑇 berlaku 𝑑(𝑇) =

𝐶(𝑇) − 1. Jika 𝑇 sebuah pohon geometrik bidang merentang semua titik poligon konveks, ditunjukkan

𝐶(𝑇) = 2 atau 𝑑(𝑇) = 1. Akhirnya, jika 𝑇 pohon geometrik bidang merentang semua titik poligon 

sederhana 𝑄 dan paling sedikit satu di interior 𝑄 dan 𝑇 bukan bintang maka 𝐶(𝑇) = 1 atau 𝑑(𝑇) = 0.

Kata kunci: Graf geometrik, Graf Bidang , Kompatibel, Poligon, Triangulasi.

Two plane geometric graphs on a set of vertices S are said to be compatible when their union is a plane 

geometric graphs on 𝑆. Given a plane geometric spanning tree 𝑇 on 𝑆. The main problem is finding

another plane geometric spanning tree 𝑇1 on S,such that 𝑇1 is 𝑇-compatible and 𝑇1 has a minimum 

number of edges in common with 𝑇. The minimum number of common edges of 𝑇 and 𝑇1, denoted by 

𝑑(𝑇). In general, determining the value of 𝑑(𝑇) is an interesting but difficult problem, since it depends 

on two things, the class of 𝑇 and the position of the vertices of 𝑇 on the plane. If T is a star, then 𝑑(𝑇) =

1. A triangulation  of 𝑇 is a graph obtained from 𝑇 by adding as much as possible new edges, namely 

red edges, to 𝑇 such that the resulting graph is still a plane geometric graph and each of its internal face is 

a triangle. Generally, a triangulation  of 𝑇 is not unique. The minimum number of components of  − 𝑇

is denoted by 𝐶(𝑇). It is proven that if 𝑇 is a plane geometrc tree, then 𝑑(𝑇) = 𝐶(𝑇) – 1. If 𝑇 is a 

plane geometric tree is spanning all vertices of a simple convex polygon, it is shown that 𝐶(𝑇) = 2 or 

𝑑(𝑇) = 1. Finally, we prove that 𝑇 is a plane geometric tree that spans all vertices of a simple polygon 

𝑄 and at least one in the interior of 𝑄 and 𝑇 is not a star, then 𝐶(𝑇) = 1 or 𝑑(𝑇) = 0.

Keywords: Geometric Graph, Plane Graph, Compatible, Polygon, Triangulation.