Max - Flow and Min - Cut, Minimize the number of visible boxes Suppose that you are given a set of boxes, with each box as a rectangular parallelepiped with side lengths as (i1, i2, i3).  And each side length is between half a meter and one meter.
How should a nesting arrangement be chosen so as to minimize the number of visible boxes?  Give a polynomial time algorithm for solving this problem.  
I've been attempting to generate a graph which would make solving this problem simple by applying the Max - Flow algorithm, but can't seem to move past just understanding needing a graph.  At first I thought matching, but then realized that more than one box can be nested in another so that doesn't work.
 A: Although this answer is (very) late, it may help future readers who are looking for an answer.
Let's assume that boxes cannot be nested side by side in the same box. Otherwise, the problem becomes NP-hard.
Create two nodes for each box. The $i^{th}$ box will be represented by node $u_i$ and node $v_i$. Put a directed edge with capacity 1 from node $u_i$ to $v_j$ iff $v_j$ can be nested in $u_i$ for $i \ne j$. Now put a directed edge of capacity 1 from a super source to $u_i$ for all $i$ and put a directed edge of capacity 1 from $v_j$ to a super sink for all $j$. Run any max flow algo from the super source to the super sink.
Notice that this gives you a maximum-bipartite matching. And what is the interpretation of this matching? For each $u_i$ that is matched with $v_j$, it means that $v_j$ can be nested in $u_i$. So the max flow is actually the maximum number of times you can put one box into a bigger one. Since every time you do so reduces the number of visible boxes by 1, the minimum number of visible boxes = number of boxes - max flow.
To get the actual nesting configuration, simply pick all the edges in the matching and nest $v_j$ into $u_i$ for every ($u_i$, $v_j$) edge present in the matching.
Let number of boxes be $n$. This solution works in $\mathcal{O}(n^3)$ if we use ford fulkerson's algorithm because by handshake lemma, we can have $\frac{n(n-1)}{2}$ edges in a complete graph and we have an additional $2n$ edges for edges to/from source and sink. So total number of edges = $\mathcal{O(n^2)}$. And max flow can be at most $\lfloor\frac{2n}{2}\rfloor = \mathcal{O}(n)$. Because that is the upper bound for the size of any matching. So number of edges * maximum flow = $\mathcal{O}(n^3)$.
