## KONSTRUKSI FAMILI GRAF HAMPIR PLANAR DENGAN ANGKA PERPOTONGAN TERTENTU
Benny Pinontoan 1)
1) Program Studi Matematika FMIPA Universitas Sam Ratulangi Manado, 95115

## ABSTRAK
Sebuah  graf  adalah  pasangan  himpunan  tak  kosong  simpul  dan  himpunan  sisi.  Graf  dapat digambar  pada  bidang  dengan  atau  tanpa  perpotongan.  Angka  perpotongan  adalah  jumlah perpotongan terkecil di antara semua gambar graf pada bidang. Graf dengan angka perpotongan nol disebut planar. Graf memiliki penerapan penting pada desain Very Large Scale of Integration (VLSI).  Sebuah  graf  dinamakan  perpotongan  kritis  jika  penghapusan  sebuah  sisi  manapun menurunkan  angka  perpotongannya,  sedangkan  sebuah  graf  dinamakan  hampir  planar  jika menghapus  salah  satu  sisinya  membuat  graf  yang  sisa  menjadi  planar.  Banyak  famili  graf perpotongan  kritis  yang  dapat  dibentuk  dari  bagian-bagian  kecil  yang  disebut  ubin  yang diperkenalkan  oleh  Pinontoan  dan  Richter  (2003).  Pada  tahun  2010,  Bokal  memperkenalkan operasi  perkalian  zip  untuk  graf.  Dalam  artikel  ini  ditunjukkan  sebuah  konstruksi  dengan menggunakan ubin dan perkalian zip yang jika diberikan bilangan bulat k 1, dapat menghasilkan famili tak hingga graf hampir planar dengan angka perpotongan k .
Kata kunci: angka perpotongan, ubin graf, graf hampir planar.

## CONSTRUCTION OF INFINITE FAMILIES OF ALMOST PLANAR GRAPH WITH GIVEN CROSSING NUMBER

## ABSTRACT
A graph is a pair of a non-empty set of vertices and a set of edges. Graphs can be drawn on the plane with or without crossing of its edges. Crossing number of a graph is the minimal number of crossings  among  all  drawings  of  the  graph  on  the  plane.  Graphs  with  crossing  number  zero  are called  planar.  Crossing  number  problems  find  important  applications  in  the  design  of  layout  of Very Large Scale of Integration (VLSI). A graph is crossing-critical if deleting of any of its edge decreases  its  crossing  number.  A  graph  is  called  almost  planar  if  deleting  one  edge  makes  the graph planar. Many infinite sequences of crossing-critical graphs can be made up by gluing small pieces,  called  tiles  introduced  by  Pinontoan  and  Richter  (2003).  In  2010,  Bokal  introduced  the operation zip product of graphs. This  paper shows a construction by using tiles and zip product, given an integer k 1, to build an infinite family of almost planar graphs having crossing number k . Keywords : Crossing number, tile, almost planar graph.

## PENDAHULUAN
Sebuah  graf  adalah  pasangan  ( N , E ) dimana N adalah  himpunan  tak  kosong  dari simpul  dan E adalah  himpunan  sisi.  Jika e = uv adalah  sebuah  sisi  dari  graf G maka simpul u dan simpul v masing-masing adalah ujung dari e , dan kedua simpul itu dinamakan tetangga  atau  saling  damping.  Dua  sisi  yang memiliki  simpul  bersama  dinamakan  sisi damping.
Graf  dapat  digambar  pada  sebuah bidang  dimana  simpul  disajikan  sebagai  titik
dan  sisi  sebagai  garis  yang  menghubungkan simpul-simpul yang menjadi ujungnya. Dalam  sebuah  gambar  dari  sebuah  graf,  dua sisi  bisa  berpotongan  atau  tidak.  Banyaknya perpotongan sisi pada sebuah gambar disebut jumlah  perpotongan. Angka  perpotongan cr ( G )  dari  sebuah  graf G adalah    jumlah perpotongan terkecil di antara semua gambar dari graf G . Sebuah graf G adalah planar jika cr ( G ) = 0, selain itu disebut nonplanar.
Di  antara  banyak  penerapannya, masalah  angka  perpotongan  menjadi  sangat
menarik  dan  penting  karena  penerapannya dalam optimalisasi daerah chip yang dibutuhkan  dalam  layout  sirkuit Very  Large Scale  of  Integration atau VLSI (Leighton, 1983 dan Sherwani, 1993). Contoh dari VLSI adalah microprocessor. Peminimalan
perpotongan  di  sini  juga  untuk  mereduksi resiko korsleting. Sifat struktural masalah angka perpotongan  dipelajari  melalui  graf-graf perpotongan-kritis.  Sebuah  graf G adalah perpotongan-kritis- k jika cr ( G ) k dan cr ( G - e )  < k untuk  setiap  sisi e dari G .  Lebih menarik  lagi  jika cr ( G ) k dan cr ( G - e )  =  0, untuk setiap sisi e dari G . Pinontoan dan Richter (2003) melakukan  konstruksi  famili  tak  hingga  dari graf perpotongan-kritis- k
dengan memperkenalkan  konsep  ubin  ( tile ).  Ubin adalah  graf  dengan  beberapa  ketentuan khusus.  Ubin-ubin  dapat  rangkaikan  dengan cara  merekatkan  satu  ubin  dengan  yang lainnya dan diatur dengan pola linear maupun lingkaran.  Rangkaian  ubin-ubin  dengan  pola lingkaran  membentuk  famili  graf  tak  hingga. Dengan  cara  ini,  angka  perpotongan  famili graf ini dapat ditentukan.
Bokal (2010) memperkenalkan operasi perkalian zip pada graf. Jika dua graf G 1 dan G 2 masing-masing mempunyai simpul v 1 dan v 2 yang memiliki jumlah tetangga yang sama  maka G 1 dan G 2 bisa  dilakukan perkalian zip pada v 1 dan v 2 .
Sebuah graf G disebut hampir planar jika G memiliki  sisi  (meskipun  tidak  setiap sisi)  yang  penghilangannya  menjadikan G planar  (Mohar,  2006).  Sisi  tersebut  disebut pemplanar .
Pertanyaan  yang  muncul  adalah: adakah konstruksi dengan menggunakan ubin dan  perkalian  zip,  yang  menghasilkan  famili tak  hingga  graf  hampir  planar  dengan  angka perpotongan  tertentu?  Dengan  kata  lain,  jika diberikan  bilangan  bulat k 1,  bagaimana mengkonstruksi famili tak hingga graf hampir planar dengan angka perpotongan k ?
Paper  ini  menyajikan  konstruksi famili  tak  hingga  graf  hampir  planar  dengan angka perpotongan tertentu.

## Angka perpotongan Graf dan Graf Hampir Planar
Sebuah gambar D( G )  dari  graf G adalah  pemetaan  dari  graf  pada  bidang
dimana simpul disajikan sebagai titik dan sisi sebagai  garis  yang  menghubungkan  simpul- simpul  yang  menjadi  ujungnya.  Perpotongan dalam sebuah gambar dari graf adalah sebuah titik  pada  bidang  yang  bukan  merupakan representasi  simpul  dimana  dua  buah  garis bertemu.
Gambar  yang  baik  dari  sebuah  graf memiliki sifat-sifat, yaitu: tidak ada sisi yang memotong  dirinya  sendiri,  dua  sisi  damping tidak  boleh  saling  memotong,  dua  sisi  tidak boleh saling memotong lebih dari sekali, dan paling banyak dua sisi berpotongan pada satu titik.  Banyaknya  perpotongan  sisi  pada sebuah  gambar  yang  baik  disebut  jumlah perpotongan. Angka  perpotongan  cr ( G )  dari sebuah  graf  adalah  jumlah  perpotongan terkecil diantara semua gambar baik dari graf G .  Gambar  sebuah  graf  dengan  jumlah perpotongan terkecil disebut gambar optimal . Graf G adalah planar jika cr ( G )  =  0  dan nonplanar  jika cr ( G ) 0.  Masalah  angka perpotongan diperkenalkan oleh Tutte (1970).
Menentukan angka perpotongan sebuah  graf  tidaklah  mudah.  Menurut  Garey dan Johnson (1983), masalah angka perpotongan merupakan masalah NP- complete.  Kuratowski  (1930)  menetapkan karakteristik  dari  graf  planar:  sebuah  graf G adalah  planar  jika  dan  hanya  jika G tidak mengandung  subdevisi  dari K 3,3 or K 5 . Biasanya, untuk membuktikan bahwa cr ( G ) k dilakukan  melalui  gambar  pada  bidang sedangkan  untuk  membuktikan  bahwa cr ( G ) k ,  dilakukan  dengan  menunjukkan  bahwa memang  terdapat k pasang  sisi  yang berpotongan.
Beberapa studi telah dilakukan tentang  angka  perpotongan  dari  famili  tak hingga  dari  graf,  terutama  famili  berikut  ini. Namun  tidak  semua  angka  perpotongan  dari famili  graf  ini  sudah  diketahui.  Hanya beberapa  anggota  dari  famili  graf  ini  yang sudah  diketahui.  Meskipun  demikian,  telah disampaikan  konjektur  dari  famili  graf tersebut sebagai berikut:
Graf lengkap ( the complete graph ) K n . Konjekturnya adalah cr ( K n ) = ¼ n /2   ( n -
1)/2 ( n -2)/2 ( n -3)/2 .  Ini  dikenal dengan konjektur Guy untuk graf lengkap (Guy, 1972). Konjektur ini telah dibuktikan  untuk n ≤  12  oleh  Pan  dan Richter (2007).
Graf  bipartite  lengkap ( the  complete bipartite  graphs ) K m , n .  Konjekturnya adalah cr ( K m , n )  = m /2   ( m -1)/2 n /2 ( n -1)/2 .  Ini  dikenal  dengan  konjektur
Zarankiewicz untuk graf bipartite (Zarankiewicz, 1954). Lomeli dan Salazar (2006)  membuktikan  untuk m ≤  6  dan semua n .
Perkalian Cartesius ( the Cartesian product ) C m × C n .
Konjekturnya  adalah cr ( C m × C n )  =  ( m – 2) n , untuk 3 ≤ m ≤ n . Ini telah dibuktikan untuk n m ( m +1)  oleh  Glebsky  dan Salazar (2004) dan juga untuk semua m ≤ 7 oleh Adamsson dan Richter (2004).
Graf G dinamakan  perpotongan- kritis- k jika cr ( G ) k dan cr ( G – e )  < k , untuk  tiap  sisi e .  Graf  perpotongan-kritis sangat  penting  untuk  dipelajari  guna  dapat mengerti  sifat-sifat  secara  struktural  dari masalah angka perpotongan. Graf perpotongan-kritis  1  hanyalah  subdivisi  dari K 5 dan K 3,3 . Širáň (1984) memberikan contoh famili  tak  hingga  graf  perpotongan-kritis k tetapi contoh ini menggunakan sisi paralel.
Kochol  (1987)  memberikan  pertama famili  tak  hingga  graf  perpotongan-kritis dengan  menggunakan  graf  sederhana  dengan angka perpotongan graf ini adalah 2. Ini juga merupakan  contoh  famili  tak  hingga  graf terkoneksi 3.
Richter and Thomassen (1993) membuktikan bahwa angka perpotongan graf perpotongan-kritis k terbatas.  Jika G graf perpotongan-kritis,  maka cr ( G )  ≤  5 k /2  +  16. Akibatnya  bahwa  jika G adalah  juga  graf regular r ,  maka r {4,  5}.  Mereka memberikan  contoh  famili  tak  hingga  graf perpotongan-kritis  3,  terkoneksi  4,  dan regular 4.
Salazar  (2003)  mengamati  bahwa dengan argument yang sama, derajat rata-rata dari anggota famili  tak hingga graf perpotongan-kritis k ,  pasti  berada  pada interval  terbuka  dan  memberikan  contoh untuk  setiap  bilangan  rasional  pada  interval [4,  6)  dapat  diperoleh  sebagai  nilai  rata-rata dari koleksi tersebut.
Mohar and Dvořák (2009) menunjukkan konstruksi untuk setiap
bilangan bulat k 171 dari graf perpotongan- kritis k . Hlinĕný  (2003)  membuktikan  bahwa graf  perpotongan-kritis  berbentuk  panjang
dan  sempit  dan  dapat  dibentuk  oleh  bagian- bagian  kecil  yang  kemudian  direkatkan menurut pola linier. Hlinĕný  (2008) kemudian  mengkonstruksikan  graf  hampir planar,  yaitu  graf  yang  bisa  dijadikan  planar dengan  hanya  menghapus  satu  sisi  dan menunjukkan bahwa derajat rata-rata graf ini bisa bilangan rasional   [ 3,2; 6-8/( k +1) ).
Pinontoan dan Richter (2003) memperkenalkan konsep ubin dan memperluas  cakupan  rataan  derajat  dari anggota  famili  tak  hingga  graf  sederhana perpotongan-kritis k ke setiap resional dalam interval [3,5; 6).
Bokal (2010) menggunakan
perluasan  ubin  dan  perkalian  zip  untuk mengkonstruksi  famili  tak  hingga  graf perpotongan-kritis  dengan  rata-rata  deraja pada  interval  (3  ;  6).  Belum  lama  ini, Hernández-Vélez,  Salazar,  dan  Thomas (2011)  memastikan  bahwa  untuk  setiap bilangan  bulat  positif k ,  kumpulan  graf sederhana perpotongan-kritis dengan rata-rata derajat enam adalah bukan tak hingga.
Sebuah graf G disebut hampir planar jika G memiliki  sisi  (meskipun  tidak  semua sisi)  yang  penghilangannya  menjadikan G planar  (Mohar,  2006).  Sisi  tersebut  disebut pemplanar .

## Ubin dan Perkalian Zip
Pada  tahun  2003,  Pinontoan  dan Richter  memperkenalkan  konsep  ubin  ( tile ).
Sebuah  ubin T =  ( G , L , R )  adalah  graf G terkoneksi  dengan  dua  barisan  simpul  yang disebut  dinding  kiri L dan  dinding  kanan R . Angka  perpotongan  ubin , tcr ( T ),  adalah minimum  jumlah  perpotongan  di  antara semua  gambar  graf G pada  persegi  [0,  1] [0, 1] pada bidang sedemikian rupa sehingga simpul-simpul dari L berada pada {0}   [0, 1] dengan  urutan  menyusut  pada  koordinat y dan  simpul-simpul  dari R berada  pada  {1}
[0,  1]  juga  dengan  urutan  menyusut  pada koordinat y .
Gambar 1 memberikan contoh sebuah ubin ( G , L , R ) dimana R = ( v 1 , v 2 , v 3 ) dan L = ( v 9 , v 10 , v 11 ).

## Gambar 1. Sebuah ubin.
Sebuah  ubin  bisa  dibalik  secara vertikal  maupun  secara  horisontal,  dan  dapat juga  dipilin.  Dua  ubin  dikatakan  kompatibel jika  dinding-dindingnya  bersesuaian.  Dua ubin  yang  kompatibel  dapat  direkatkan dengan  operasi  perekatan.  Lebih  tepatnya, jika T 1 =  ( G 1 , L 1 , R 1 )  dan T 2 =  ( G 2 , L 2 , R 2 ) adalah  dua  ubin,  maka T 1 dikatakan kompatibel dengan T 2 jika  ada  fungsi  satu- satu f dari R 1 ke L 2 sehingga  jika v 1 , v 2 R 1 dan v 1 v 2 adalah  sisi  di T 1 maka f ( v 1 ) f ( v 2 ) adalah  sisi  di L 2 .  Jika T 1 =  ( G 1 , L 1 , R 1 ) kompatibel dengan T 2 = ( G 2 , L 2 , R 2 ), maka R 1 dan L 2 bisa direkatkan sehingga untuk semua v R 1 , v = f ( v )  dan untuk  semua  sisi v 1 v 2 T 1 dimana v 1 , v 2 R 1 , v 1 v 2 = f ( v 1 ) f ( v 2 ). Proses perekatan  ini  menghasilkan  ubin  yang  lebih besar T 1 T 2 = ( G 1 G 2 , L 1 , R 2 ).
Ubin adalah planar jika pada gambar ubin di atas bidang tidak terdapat perpotongan.  Jika  terdapat  perpotongan, maka  ubin  tersebut  adalah  nonplanar.  Ubin- ubin  planar  bersama  ubin  yang  dipilin  bisa direkatkan  dalam  aransemen  lingkaran  atau linier  sehingga  membentuk  famili  graf dengan angka perpotongan konstan (Pinontoan  dan  Richter,  2003)  sedangkan ubin-ubin  nonplanar  dengan  aransemen  yang sama  dapat  membentuk  famili  graf  dengan angka  perpotongan  tidak  konstan  (Pinontoan dan Richter, 2004).
Sebuah ubin T dinamakan swakompatibel  jika T kompatibel  terhadap dirinya sendiri. Jika  swakompatibel, maka T n diperoleh  dengan  merekatkan n kopi  dari T dalam pola linier. Sedangkan  o( T n ) diperoleh dengan  merekatkan  dinding  kiri  dan  dinding kanan dari T n sehingga membentuk lingkaran. Perhatikanlah bahwa T n adalah ubin sedangkan o( T n ) adalah graf. Jika ubin pilin Ť diperoleh  dari T =  ( G , L , R )  dengan membalikkan urutan R , maka T ( n ) = o( T n Ť ).
Teorema  1. (Pinontoan  dan  Richter,  2003). Jika  T  adalah  ubin  planar,  maka  tcr(Ť) = cr ( T ( n )) untuk nilai n yang besar.
Lebih lanjut, jika T = ( G , L , R ) maka ubin flip  horizontal  T =  ( G , R , L ),  yaitu diperoleh dari T dengan menukarkan dinding kiri  dengan  dinding  kanannya.  Sedangkan ubin flip  vertikal T dari  ubin T adalah  ubin yang  diperoleh  dari T dengan  membalikkan urutan L dan urutan R .
Misalkan T adalah  ubin  yang  umum. Angka perpotongan rata-rata ( average crossing  number ) acr ( T ) dari  ubin T didefinisikan sebagai  lim n tcr ( T n )/ n . Telah diketahui  bahwa acr ( T )  dari  ubin T bisa merupakan  bilangan  rasional  (Pinontoan, 2006).
Teorema  2. (Pinontoan  dan  Richter,  2004). Untuk  setiap  ubin  T , acr ( T ) ada  dan  sama dengan lim n cr (o( T n ))/ n .
Bokal (2010) memperkenalkan teknik  aransemen  dengan  menggunakan perkalian  zip  ( zip - product ).  Perkalian  zip adalah  sebuah  operasi  pada  graf  dan gambarnya  dengan  kondisi  tertentu  selingga mempertahankan  angka  perpotongan  dan kekritisan.
Definisi 1 (Perkalian zip, G 1 f G 2 ( v 1 , v 2 )) Untuk dua graf G i ( i = 1, 2) dengan himpunan simpul N i , dan v i G i masing-masing dengan derajat yang sama dan fungsi bijeksi f : N 1 N 2 ,  dinamakan  fungsi  zip,  dari  tetangga N i dari v i .  Perkalian  zip G 1 f G 2 ( v 1 , v 2 )  dari G 1 dan G 2 menurut f adalah ( G 1 – v 1 )   ( G 2 – v 2 ) { uf ( u ) | u N 1 }.
Gambar 2 mengilustrasikan perkalian zip G 1 dan G 2 pada v 1 dan v 2 (Gambar 2(a)). Simpul-simpul u ij ( i = 1, 2 dan j = 1, 2, 3, 4) adalah tetangga dari v i . Fungsi zip f ( u 1 j ) = u 2 j , dimana j = 1, 2, 3, 4. Hasil dari produksi zip ini  adalah  ( G 1 – v 1 ) ( G 2 – v 2 )  dengan menambahkan  sisi-sisi u 1 j u 2 j ( j =  1,  2,  3,  4) seperti  pada  Gambar  2(b).  Perhatikan  bahwa simpul v 1 dan simpul v 2 hilang.
v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 11 v 9 v 10
Gambar 2. Perkalian zip graf G 1 dan graf G 2 pada simpul v 1 dan simpul v 2 .
Lemma 1. (Bokal, 2010). Untuk i = 1, 2, misalkan G i adalah graf dan D i adalah gambar optimal dari G i , serta v i V ( G i ) adalah simpul dengan derajat d , dan misalkan f adalah fungsi zip dari D 1 dan D 2 pada v 1 dan v 2 . Maka, cr ( G 1 f G 2 ( v 1 , v 2 )) ≤ cr ( G 1 ) + cr (G 2 ).

## Konstruksi Famili Graf Hampir Planar Dengan Angka Perpotongan Tertentu
Sebelum  mengkonstruksi  famili  tak hingga  graf  hampir  planar  dengan  angka perpotongan tertentu, kita
akan mendefinisikan  beberapa  operasi  berkaitan dengan  perkalian  zip  dan  ubin  khusus  serta fungsi zip.
Definisi 2 ( f T ( u , v )) Jika T adalah  ubin, u dan v adalah  simpul- simpul  pada T ,  serta f adalah  fungsi  zip.
Maka f T ( u , v ) adalah perkalian zip dari T ke dirinya sendiri pada u dan v sesuai fungsi f .
Definisi 3 ( f T n ( u , v )) Jika T adalah  ubin, u dan v adalah  simpul- simpul  pada T ,  serta f adalah  fungsi  zip.
Maka f T n ( u , v ) adalah perkalian zip dari n ( n 2)  salinan  ubin T pada  salinan u dan v sesuai fungsi f .
Definisi 4 (Ubin H m dan ubin D m ).
Ubin H m ( m 3) adalah (( V , E ), L , R ) dimana V = { u , v 1 , v 2 , …, v m , v },
E = { uv i | i = 1, 2, …, m }   { vv i | i = 1, 2, …,
m }   { v i v i +1 | i = 1, 2, …, m – 1},
L = { u }, dan R = { v }.
Sedangkan ubin D m ( m 3) = H m { v 1 v m }.
Gambar 3 menyajikan Ubin H 5 dan D 5 .
v 3 D 5 v 5 v 4 v 2 v v 1 u v 3 H 5 v 5 v 4 v 2 v v 1 u u 11 u 12 u 13 u 14 (b) v 11 v 12 v 13 v 14 v 11 G 2 G 1 v 2 v 1 u 11 u 12 u 13 u 14 (a) v 12 v 14 v 13
Definisi 5 (Fungsi zip  ).
Misalkan T 1 dan T 2 masing-masing  adalah salinan dari ubin H n atau D n dan V i = { u i , v i 1 , v i 2 , …, v in , v i } pada T i ( i = 1, 2) adalah salinan V = { u , v 1 , v 2 , …, v n , v } pada H n dan/atau D n .
Maka   adalah fungsi satu-satu dari V 1 ke V 2 , dimana  ( v 1 j ) = v 2 j ( j = 1, 2, ..., n ).
Sebagai contoh, Gambar 4 menampilkan D 5 H 5 ( u , v ).
Gambar 4. Perkalian zip ubin D 5 dan H 5 .
Gambar 5. Famili graf hampir planar G 5 , 8 .
Teorema 3 .
Diberikan  bilangan  bulat k 1,  maka  ada famili  tak  hingga  graf  hampir  planar  dengan angka perpotongan k .
Bukti : Biarkan k 1. Pandang ubin-ubin D m dan H m ( m 3) dari Definisi 4 serta fungsi zip   dari Definisi  5.  Maka T m , n = H m n ( u , v )  adalah ubin  besar  sebagai  hasil  perkalian  zip n salinan dari ubin H m . Kemudian D m dikalikan zip dengan T m , n , maka kita peroleh ubin besar S m , n = D m ( H m n ( u , v ))( u , v ).  Dengan menerapkan  perkalian  zip  sendiri  pada  ubin S m , n pada u dan v dengan  fungsi  zip  ,  kita peroleh  graf G m,n = ( S m , n )( u , v ).  Gambar  5 menampilkan ( S 5,8 )( u , v ). G m,n terdiri  dari m siklus-( n +1)  dan  satu  siklus- m .  Ini  bisa diperoleh  dari  graf  perkalian  Cartesius C m C n +1 dari m siklus- n dengan n +1  siklus- m dengan  membuang  masing-masing  satu  dari setiap  siklus- m yang  menghubungkan  dua siklus-( n +1)  yang  sama.  Diketahui  bahwa
konjektur cr ( C m × C n +1 ) = ( m – 2)( n +1), maka dengan  membuang n sisi  yang  membuat perpotongan,  yang  tersisa  adalah  satu  sisi yang  memotong m -2  sisi  dan  inilah  angka perpotongan cr ( G m,n )  = m -2.  Karena m 3 dan k 1,  dan  dengan  menyatakan k = m -2, maka  famili  tak  hingga  ini  memiliki  angka perpotongan k .
Sangatlah  mudah  dilihat  bahwa dengan  menghapus  sisi  yang  merupakan salinan v 1 v m (sisi  ini  yang  membedakan D m dari H m ),  maka  kita  peroleh  graf  planar.
Sehingga sisi v 1 v m adalah sisi pemplanar.

## KESIMPULAN DAN SARAN
Jika  diberikan  bilangan  bulat k 1, maka  dengan  menggunakan  ubin  dan perkalian  zip,  dapat  dikonstruksi  famili  tak hingga  graf  hampir  planar  dengan  angka perpotongan k .
Namun graf yang ditunjukkan di sini bukanlah perpotongan-kritis. Pertanyaan
yang  timbul  adalah:  Jika  diberikan  bilangan bulat k 1,  adakah  famili  tak  hingga  graf hampir planar yang juga sekaligus perpotongan-kritis k ?  Jika  famili  seperti  itu ada,  bisakah itu dikonstruksikan  dengan  cara seperti  ini?  Hal  ini  bisa  menjadi  bahan penelitian selanjutnya.

## DAFTAR PUSTAKA
Adamsson,  J.,  and  R.B.  Richter.      2004. Arrangements and the Crossing Numbers  of C m × C n . J . Combin. Theory ( B ) 90 , 21-39.
Bokal,  D.    2010.    Infinite  Families  of
Crossing-Critical Graphs with Prescribed Average Degree and Crossing  Number. J.  Graph  Theory
65 , 139-162.
Chartrand, G. and L. Lesniak. 1996. Graphs
& Digraphs . Chapman & Hall/CRC.
Garey,  M.R.,  and  D.S.  Johnson.  1983. Crossing  Number  is  NP-Complete. SIAM J . Algebraic Discrete Methods 4 , 312-316.
Glebsky,  L.Y.,  and  G.  Salazar.    2004.    The Crossing  Number  of C m × C n is  as Conjectured for n m ( m +1). J. Graph Theory 47 , 53-72.
Gross,  J.L.  and  T.  W.  Tucker.  1987. Topological  Graph  Theory .    Dover,
New York. Guy,  R.K.  1972.  Crossing  Numbers  of Graphs. Graph Theory and Applications: Proceedings of  the
Conference  at  Western  Michigan University,  Kalamazoo,  Mich.,  May 10-13,  1972 (Ed.  Y. Alavi,  D. R. Lick, and A. T. White). New York: Springer- Verlag, pp. 111-124.
Hernández-Vélez,  C.,  G.  Salazar,  and  R.
Thomas.    2011. Nested  Cycles  in Large  Triangulations  and  Crossing- Critical Graphs, Submitted.
Hlinĕný,  P.  2003.  Crossing  Number  Critical Graph  Have  Bounded  Path-with. J. Combin. Theory ( B ) 88 , 347-367.
Hlinĕný, P.  2008.  New Infinite Families of Almost-Planar Crossing-Critical
Graphs. Electronic  J.  Combin. 15 , R102.
Kochol,  M.    1987.      Construction  of Crossing-Critical  Graphs. Discrete Math. 66 , 311-313.
Kuratowski,  K.    1930.    Sur  le  Problème  des
Courbes Gauches en Topologie.
Fund. Math. 15 , 271-283.
Leighton,  F.T.    1983. Complexity  Issues  in VLSI:  Optimal  layouts  for  the  Shuffe- exchange  graph  and  other  networks. MIT Press.
Mohar,  B.,  and  Dvořák.    2009.    Crossing- Critical  Graphs  with  Large  Maximum Degree, Manuscript.
Mohar, B. 2006. On the Crossing Number of Almost Planar Graphs. Informatica 30, 301-303.
Pan, S. and R.B. Richter. 2007. The Crossing Number  of K 11 is  100. J.  Graph Theory 56 , 105-112.
Pinontoan,  B.  2006.  Tile  with  Rational Average Crossing Number. J . Indones. Math. Soc. ( MIHMI ) 12 , 83-87.
Pinontoan,  B  and  R.B.  Richter.  2004. Crossing  Numbers  of  Sequences  of Graphs IG: General Tiles. Autralas. J. Combin. 30 , 197-206.
Pinontoan,  B.  and  R.B.  Richter.  2003. Crossing  Numbers  of  Sequences  of Graphs  II:  planar  tiles. J.  Graph Theory 42 , 332-341.
Richter,  R.B.,  and  C.  Thomassen.  1993.
Minimal Graphs with Crossing Number At Least k. J. Combin. Theory ( B ) 58 , 127-224.
Salazar,  G.  2003.  Infinite  Families  of Crossing-Critical  Graphs  with  Given Average  Degree. Discrete  Math. 271 ,
343-350.
Sherwani,  N.A.  1995. Algorithm  for  VLSI physical  design  automation .  Kluwer Academic  Publishers,  Massachusetts, USA.
Širáň, J. 1984. Infinite Families of Crossing- Critical  Graphs  with  Given  Average Degree. Discrete Math. 48 , 129-132.
Tutte,  W.T.  1970.  Toward  a  Theory  of Crossing Numbers. J. Combin. Theory 8 , 45-53.
Wilson,  R.J.  1996. Graph  Theory .  Prentice
Hall, New York.
Zarankiewicz,  K.  1954.  On  a  Problem  of P. Turán  Concerning  Graphs. Fund.
Math. 41 , 137-145.