Puzzling Grid Embeddings

Abstract

We present a pipeline that, given a weighted graph as an input, produces a planar grid embedding where all edges are represented as axis-aligned straight lines with their Euclidean length matching their edge weight (if such an embedding exists). Being able to compute such embeddings is important for visualization purposes but is additionally helpful to solve certain optimization problems faster, as e.g. the Steiner tree problem. Our embedding pipeline consists of three main steps: In the first step, we identify rigid substructures which we call puzzle pieces. In the second step, we merge puzzle pieces if possible. In the third and last step, we compute the final embedding (or decide that such an embedding does not exist) via backtracking. We describe suitable data structures and engineering techniques for accelerating all steps of the pipeline along the way. Experiments on a large variety of input graphs demonstrate the applicability and scalability of our approach.