Self-avoiding walks over adaptive unstructured grids

In this paper, we present self-avoiding walks as a novel technique to 'line arize' an unstructured mesh, Unlike space-filling curves which are based on a geometric embedding, our strategy is combinatorial since it uses the mes h connectivity only, We formulate a linear time-complexity algorithm for th e construction of these self-avoiding walks over a triangular mesh. We also show how the concept can be easily modified for adaptive grids that are ge nerated in a hierarchical manner based on a set of simple rules, and made a menable for Efficient parallelization. We suggest a metric that might be us ed to evaluate the quality of such walks and present some sample results, T he proposed locality-enhancing approach should be very useful in the runtim e partitioning and load balancing of adaptive unstructured grids. Copyright (C) 2000 John Wiley & Sons, Ltd.