Photo collage is an effective representation for photo summarization and visualization. However, its practical usage is limited by its high computational cost. In this paper, we present efficient optimization techniques based on a novel formulation on markov random fields and several insights unexploited by previous approaches. Our method achieves up to hundreds-fold performance improvement, and user/application specific constraints can be easily integrated. We present new applications including interactive collage refinement and dynamic collage for photo browsing. Preliminary evaluation and user study indicates that our approach extends the usability of photo collage.