K-CROSSING CRITICAL ALMOST PLANAR GRAPHS

Abstract

K-CROSSING CRITICAL ALMOST PLANAR GRAPHS

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 crossing among all drawings of the graph on the plane. Graphs with crossing number zero are called planar. A graph is crossing critical if deleting any of its edge decreases its crossing number. A graph is called almost planar if deleting one edge makes the graph planar. This research shows graphs, given an integer k ≥ 1, to build an infinite family of crossing critical almost planar graphs having crossing number k.

Keywords: Almost planar graph,crossing critical graph.

GRAF K-PERPOTONGAN KRITIS HAMPIR PLANAR

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.  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.  Dalam penelitian ini ditunjukkan graf, yang jika diberikan bilangan bulatk≥1, dapat menghasilkan famili takhingga graf perpotongan kritis hampir planar dengan angka perpotongan k.

Kata kunci: Graf hampir planar, graf perpotongan kritis.