<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
Radio Channel Assignment on 2-Dimensional Lattices
J. van den Heuvel
Department of Mathematics, Centre for Discrete and Applicable Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, UK
Annals of Combinatorics 6 (3) p.463-477 September, 2002
AMS Subject Classification: 05C78, 90C35
Given a set V of points in the plane, a sequence d0, d1, ..., dk of nonnegative numbers and an integer n .we are interested in the problem to assign integers from {0,..., n-1} to the points in Vsuch that if are two points with Euclidean distance less than di, then the difference between the labels of is not equal to i. This question is inspired by problems occurring in the design of radio networks, where radio channels need to be assigned to transmitters in such a way that interference is minimized. In this paper we consider the case that the set of points are the points of a 2-dimensional lattice. Recent results by McDiarmid and Reed show that if only one constraint d0 is given, good labellings can be obtained by using so-called strict tilings. We extend these results to the case that higher level constraints d0, d1, ..., dk occur. In particular we study conditions that guarantee that a strict tiling, satisfying only the one constraint d0, can be transformed to a strict tiling satisfying the higher order constraints as well. Special attention is devoted to the case that the points are the points of a triangular lattice.
Keywords: radio channel assignment, optimal labelling, Euclidean distance, minimum span, 2- dimensional lattice, strict tiling


1. J.-F. Arnaud, Frequency planning for broadcast services, Europ. Proc. IEEE 68 (1980) 1515每 1522.

2. M. Bernstein, N.J.A. Sloane, and P.E. Wright, On sublattices of the hexagonal lattice, Discrete Math. 170 (1997) 29每39.

3. S.J. Curran and J.A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs 〞A survey, Discrete Math. 156 (1996) 1每18.

4. H. Daud谷, P. Flajolet, and B. Vall谷e, An average-case analysis of the Gaussian algorithm for lattice reduction, Combin. Probab. Comput. 6 (1997) 397每433.

5. J.J. David, Determination of progression steps in lattice planning method, IEEE Trans. Broadcast. 35 (1989) 307每313.

6. A. Gamst, Homogeneous distribution of frequencies in a regular hexagonal cell system, IEEE Trans. Veh. Tech. VT-31 (1982) 132每144.

7. J.P. Georges and D.W. Mauro, Generalized vertex labelings with a condition at distance two, Congr. Numer. 109 (1995) 141每159.

8. J.R. Griggs and R.K. Yeh, Labeling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586每595.

9. M. Grötschel, L. Lov芍sz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd Ed., Springer-Verlag, Berlin, 1993.

10. W.K. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (1980) 1497每 1514.

11. J. van den Heuvel, R.A. Leese, and M.A. Shepherd, Graph labelling and radio channel assignment, J. Graph Theory 29 (1998) 263每283.

12. J.C. Lagarias, Point lattices, In: Handbook of Combinatorics, R.L. Graham, M. Gr“otschel, and L. Lov∩asz, Eds., Elsevier, Amsterdam, 1995, pp. 919每966.

13. R.A. Leese, A unified approach to the assignment of radio channels on a regular hexagonal grid, IEEE Trans. Veh. Tech. 46 (1998) 968每980.

14. V.H. MacDonald, The cellular concept, Bell System Tech. J. 58 (1979) 15每41.

15. C. McDiarmid and B. Reed, Colouring proximity graphs in the plane, Discrete Math. 199 (1999) 123每137.

16. D. Witte and J.A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51 (1984) 293每304.