Gerrymandering is the manipulation of political districts to advantage or oppress a particular group. To understand whether districts have been egregiously manipulated, one must obtain baseline outcomes in the absence of manipulation. There is a growing consensus to establish such baselines by sampling a representative policy-based collection of alternative and neutral redistricting plans. Sampling the space of redistricting plans may be recast as sampling a space of graph partitions on a (mostly) planar graph over some family of probability distributions. Although several research groups have made a number of compelling advances in sampling, there remains a wide chasm between the distributions we are able to sample and the distributions we would like to sample, i.e. we can understand the typical behavior of some policies, but not others. In this talk, I will discuss the redistricting problem along with several novel sampling techniques developed by our research group. These techniques expand the family of distributions (and policies) that we can efficiently sample and include both multi-scale methods and work in parallel tempering.