To layout a passive optical network (PON) under the constraints of cost effectiveness is essentially a constraint optimization problem. In this paper, we first show that in general this problem is hard not solvable in polynomial time. We then follow it up by exploiting certain graph theoretical techniques and proposing an algorithm that produces an effective layout for PONs. We verify our results via an experimental methodology, where our proposed approach performs extremely well compared to randomized layouts.