Numerical methods associated with graph-theoretic image processing
algorithms often reduce to the solution of a large linear system. We
show here that choosing a topology that yields a small graph diameter
can greatly speed up the numerical solution. As a proof of concept, we
examine two image graphs that preserve local connectivity of the nodes
(pixels) while drastically reducing the graph diameter. The first is
based on a ``small-world'' modification of a standard 4-connected
lattice. The second is based on a quadtree graph. Using a recently
described graph-theoretic image processing algorithm we show that
large speed-up is achieved with a minimal perturbation of the solution
when these graph topologies are utilized. We suggest that a variety of
similar algorithms may also benefit from this approach.