This thesis is concerned with problems encountered in image-based rendering (IBR) systems. The significance of such systems is increasing as virtual reality as well as augmented reality are finding their way into many applications, from entertainment to military. Particularly, I propose methods that are based on graph theory to address the open problems in the literature of image and video compositing, and scene completion. For a visually plausible compositing, it is first required to separate the object to be composed from the background it was initially captured against, a problem that is known as natural image matting. It aims, using some user interactions, to calculate a map that depicts how much a background color(s) contributes to the color of every other pixel in an image. My contributions to matting increase the accuracy of the map calculation as well as automate the whole process, by eliminating the need for user interactions. I propose several techniques for sampling user interactions which enhance the quality of the calculated maps. They rely on statistics of non-parametric color models as well as graph transduction and iterative graph cut techniques. The presented sampling strategies lead to state-of-the-art separation, and their efficiency was acknowledged by the standard benchmark in the literature. I have adopted the Gestalt laws of visual grouping to formulate a novel cost function to automate the generation of interactions that otherwise have to be provided manually. This frees the matting process from a critical limitation when used in rendering contexts. Scene completion is another task that is often required in IBR systems. This document presents a novel image completion method that overcomes a few drawbacks in the literature. It adopts a binary optimization technique to construct an image summary, which is then shifted according to a map, calculated with combinatorial optimization, to complete the image. I also present the formulation with which the proposed method can be extended to complete scenes, rather than images, in a stereoscopically and temporally-consistent manner.