  Given a graph $G = (V,E)$ with vertex weights $w(v)$ and a desired number of
parts $k$, the goal in graph partitioning problems is to partition the vertex
set V into parts $V_1,\ldots,V_k$. Metrics for compactness, contiguity, and
balance of the parts $V_i$ are frequent objectives, with much existing
literature focusing on compactness and balance. Revisiting an old method known
as striping, we give the first polynomial-time algorithms with guaranteed
contiguity and provable bicriteria approximations for compactness and balance
for planar grid graphs. We consider several types of graph partitioning,
including when vertex weights vary smoothly or are stochastic, reflecting
concerns in various real-world instances. We show significant improvements in
experiments for balancing workloads for the fire department and reducing
over-policing using 911 call data from South Fulton, GA.
