Graph partitioning is a theoretical subject with applications inmany areas, principally: numerical analysis, programs mapping ontoparallel architectures, image segmentation, VLSI design. During thelast 40 years, the literature has strongly increased and bigimprovements have been made. This book brings together the knowledge accumulated during manyyears to extract both theoretical foundations of graph partitioningand its main applications.