On the 2-Dimensional Channel Assignment Problem

D. T. Lee, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We consider the 2-dimensional channel assignment problem: given a set S of iso-oriented rectangles (whose sides are parallel to the coordinate axes), find a minimum number of planes (channels) to which only nonoverlapping rectangles are assigned. This problem is equivalent to the coloring problem of the rectangle intersection graph G = (V, E), in which each vertex in V corresponds to a rectangle and two vertices are adjacent iff their corresponding rectangles overlap, and we ask for an assignment of a minimum number of colors to the vertices such that no adjacent vertices are assigned the same color. We show that the problem is NP-hard.

Original languageEnglish (US)
Pages (from-to)2-6
Number of pages5
JournalIEEE Transactions on Computers
Issue number1
StatePublished - Jan 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


  • 2-dimensional channel assignment
  • NP-completeness
  • coloring problem
  • rectangle intersection graphs


Dive into the research topics of 'On the 2-Dimensional Channel Assignment Problem'. Together they form a unique fingerprint.

Cite this