We will demonstrate a new partitioning approach, based on graph theory, that applies to both irregularly weighted structured grids and irregularly coupled structured multi-block grids. As case studies, we will give partitioning results from two real life applications, the Baltic sea and a multi-element wing profile Airbus 310. In the Baltic sea application we have irregular workload due to varying sea depth and in the wing application we have a multi-block grid with irregular couplings between the blocks. Finally, we will give some experimental results comparing different partitioning strategies for multi-block grids. We have used a two dimensional Navier-Stokes solver on a 512 processor Cray T3D and a 64 processor Cray T3E-900.