Optimal coloring of a plane using unit distance graphs
Date
2012
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science and Information Technology
Abstract
Generally, plane coloring is the assignment of different colors to different points of a plane.
Plane can be represented via graphs and hence can be colored using graph coloring. So the
chromatic number of a plane is equivalent to finding the chromatic number of the equivalent graph of the plane. The unit distance graph can be used to find the chromatic number of a plane. The main application of unit distance graphs is the unit distance wireless networks (UDW), in cellular networks; the geometric regions are partitioned into hexagonal cells. Unit
distance graph can represent the hexagonal cells, and coloring the hexagonal regions implies
distribution of frequencies among the hexagonal cells. Different heuristic based algorithms viz. contraction based RLF, DSATUR and IDO based graph coloring algorithms are used in
this study in order to color the unit distance graphs. And, different simple unit distance graphs used during the study include wheel graph, cycle graph, grid graph, etc. as test cases for these coloring algorithms.
The optimality of plane coloring, nowadays, is no more just confined to the minimal number of colors rather the coloring time makes importance. Since, coloring time is important in the field of cellular networks as the assignments of the frequency in a geometric regions and assignment of data to registers in program execution in minimum time. Since, these problems can be resolved through graph coloring. In this context, this study analyzes on optimal
coloring of planes using heuristic based approaches so as to suggest an effective coloring
paradigm.
Description
Keywords
Optimal coloring, Heuristic algorithm