The efficient solution of many large-scale scientific calculations depends on adaptive mesh strategies. We present new parallel algorithms to solve two significant problems that arise in this context: the generation of the adaptive mesh and the mesh partitioning. The crux of our refinement algorithm is the identification of independent sets of elements that can be refined in parallel. The objective of our partitioning heuristic is to construct partitions with good aspect ratios. We present run-time bounds and computational results obtained on the Intel DELTA for these algorithms. These results demonstrate that the algorithms exhibit scalable performance and have run-times small in comparison with other aspects of the computation.< >