Box-Depth Problem:
Given $n$ rectangles, such that their sides are parralel to the coordinate axes ($x$ and $y$), Find a subset with maximum size such that the intersection of its members are not empty.
Max-Clique Problem:
A simple graph $G$ is given. What is the size of the biggest complete subgraph (clique) of $G$?
Question:
Polynomially Reduce Box-Depth Problem to Max-Clique Problem. (Provide a translation function)
Note: I was thinking of seeing a rectangle as a clique with $4$ nodes... But, This doesn't work out... Because this way, All of the cliques are of size $4$, and the answer to the problem would be always $4$... which is incorrect.
Hint.
You want to build a graph whose nodes are the rectangles. Two nodes are connected by an edge when the rectangles intersect.
How can you tell if a pair of rectangles intersect? Can you decide that for all pairs of rectangles in polynomial time?
Edit: My second thoughts led me to doubt this solution. A clique in the graph is set of rectangles each pair of which intersect, but the question calls for a set with an empty intersection.
My third thoughts are that this is not a problem. For arbitrary rectangles, three can intersect in pairs without having a common point. But I am pretty sure you can prove that for any finite set of rectangles with axes parallel to the coordinate axes, pairwise intersection implies intersection. I'll leave it up as a cautionary tale.