Abstract: On the Embedding of Refinements of 2-dimensional Grids

Fabricio d'Amore, Luca Becchetti, Sergej L. Bezrukov,
Alberto Marchetti-Spaccamela, Mauro Ottaviani, Robert Preis
Markus Röttger, Ulf-Peter Schroeder

We consider the problem of constructing embeddings of 2-dimensional FEM graphs into grids. Our goal is to minimize the edge-congestion and dilation and optimize the load. We introduce some heuristics, analyze their performance, and present experimental results comparing the heuristics with the methods based on the usage of standard graph partitioning libraries.

Keywords: Embeddings, grids, finite elements method, graph partitioning.