An Introduction to Intersection Graphs

An Introduction to Intersection Graphs

Madhumangal Pal (Vidyasagar University, India)
DOI: 10.4018/978-1-5225-9380-5.ch002

Abstract

In this chapter, a very important class of graphs called intersection graph is introduced. Based on the geometrical representation, many different types of intersection graphs can be defined with interesting properties. Some of them—interval graphs, circular-arc graphs, permutation graphs, trapezoid graphs, chordal graphs, line graphs, disk graphs, string graphs—are presented here. A brief introduction of each of these intersection graphs along with some basic properties and algorithmic status are investigated.
Chapter Preview
Top

Introduction

The graphs are very useful tool to model a huge number of real life problems starting from science, technology, medical science, social science and many other areas. The geometrical and topological stuctures of any communication system such as Internet, Facebook, Whatsapp, ResearchGate, Twiter, etc. are based on graph. So graph theory is an old as well as young topic of research as till today graphs are used to solve several problems. Depending on the geometrical structures and properties different type of graphs are defined, viz. path, cycle, tree, complete graph, planar graph, perfect graph, chordal graph, tolarence graph, intersection graph, etc.

Table 1.
Table of abbreviations
AbbreviationDescription
IntGIntersection graph
InvGInterval graph
CirGCircular-arc graph
PerGPermutation graph
TraGTrapezoidal graph
TolGTolerance graph
PCAProper circular-arc
UCAUnit circular arc
GIGGrid intersection graphs

In this chapter, diferent types of intersection graphs (IntGs) are defined and investigated their properties.

Let 978-1-5225-9380-5.ch002.m01 be a finite or infinite set of sets. For each set 978-1-5225-9380-5.ch002.m02 we consider a vertex (978-1-5225-9380-5.ch002.m03) and there is an edge between the vertices 978-1-5225-9380-5.ch002.m04 and 978-1-5225-9380-5.ch002.m05 if the corresponding sets 978-1-5225-9380-5.ch002.m06have a non-empty intersection. That is, the set of vertices 978-1-5225-9380-5.ch002.m07 and the set of edges

978-1-5225-9380-5.ch002.m08
.

The resultant graph is called intersection graph.

Complete Chapter List

Search this Book:
Reset