A Graph Theoretic Approach for Channel Assignment in Cellular Networks

We define a cellular assignment graph to model the channel assignment problem in a cellular network where overlapping cell segments are included in the model. Our main result is the Capacity-Demand Theorem which shows a channel assignment function is always possible unless there is a connected subregion of cells and overlap segments containing more channel requests then the total capacity of all transceivers within or on the boundary of the subregion and covering any part of the subregion with an overlapping segment. We further describe the simplicity and regularity of our proposed cellular assignment graphs and their accessibility for simulation and theoretical investigation without artifacts from the overall geographical region boundaries.