Colouring and Labelling of Planar Graphs: (Extended Abstract)
Jan van den Heuvel, Sean McGuinness · 1998
Graph colouring and labelling has been an important tool in the mathematical study of Frequency Assignment Problems (FAP's). The underlying idea is that a collection of transmitters or base stations and their mutual interference can be represented by a graph. This graph has the collection of transmitters as its vertices and two vertices are connected by an edge if their mutual interference is large. A further assumption in this model is that the distance of two transmitters in the graph (the length of the shortest path between the two vertices) gives a good indication of the mutual interference between the two transmitters. When the FAP originates as a problem in a cellular network, with the cells being regions in the plane, the graph obtained as above is very likely to be a planar graph or a graph that is “close” to being planar. Because of this it is surprising that no research on labelling with distances has been done specifically for planar graphs. The aim of this note is to start filling this gap.