We solve the Union-Find problem (UF) efficiently for
the case the input is restricted to several graph
classes, namely partial k-trees for any fixed k,
d-dimensional grids for any fixed dimension d and
for planar graphs. For the later we develop a technique
of decomposing such a graph into small subgraphs,
patching, that might be useful for other algorithmic
problems on planar graphs, too. By efficiency we do not
only mean "linear time" in a theoretical setting but
also a practical reorganization of memory such that a
dynamic data structures for UF is allocated
consecutively and thus to reduce the amount of page
fault produced by UF implementations drastically.
