Graph contraction is applied in many areas of computer science, for instance, as a subprocess in parallel graph partitioning.
Parallel graph partitioning is usually implemented as a poly-algorithm intended to speed up the solving of systems of linear
equations. Image analysis is another field of application for graph contraction. There regular and irregular image hierarchies
are built by coarsening images.
In this paper a general structure of (multilevel) graph contraction is given. The graphs of these coarsening processes are
given a topological structure which allows to use concepts like the neighborhood, the interior and the boundary of sets in
a well-defined manner. It is shown in this paper that the various coarsenings used in practice are continuous and therefore
local processes. This fact enables the efficient parallelization of these algorithms. This paper also demonstrates that the
efficient parallel implementations which already exist for multilevel partitioning algorithms can easily be applied to general
image hierarchies.
This work was supported by the Austrian Science Fund (Österreichischer Fonds zur Förderung der wissenschaftlichen Forschung).