Rectangle number for hypercubes and complete multipartite graphs
張宜武, Yi-Wu Chang · 1998
The rectangle number of a graph G is the minimum t such that G is the intersection graph of sets that are unions of t rectangles in the plane with vertical and horizontal sides We prove that complete multipartite graphs have rectangle number at most two and that the k dimensional hypercube has rect angle number at most dk e except one more when k