Bibliographic Information: Appeared in Special issue of Theoretical Computer Science for COCOON'98, volume 261, issue 2, 2001, pp. 253-266
An extended abstract appeared in Proceedings of the 4-th Annual International Computing and Combinatorics Conference - COCOON, 1998.
We obtain the following result: Let $G$ be a well-shaped mesh in $d$ dimensions. Then $G$ can be partitioned in $k$ subgraphs $G_1$,...,$G_k$ such that for all $i$ in the range $1\leq i\leq k$, $G_i$ has $\Theta(n/k)$ vertices and the number of edges connecting $G_i$ with other subgraphs is bounded by $O(n/k)^{1-1/d}$. Similar results (with $d = 2$) are also given for planar graphs and graphs with bounded genus and forbidden minors. Furthermore, our algorithm can find such a partition in $O(n\log k)$ time. We also extend this result to weighted graphs and vertex-based graph decomposition. You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.