Enumerating Grid Layouts of Graphs

Abstract

We study algorithms that generate layouts of graphs with $n$ vertices in a square grid with $\nu$ points, where adjacent vertices in the graph are also close in the grid. The problem is motivated by graph drawing and factory layout planning. In the latter application, vertices represent machines, and edges join machines that should be placed next to each other. Graphs admitting a grid layout where all edges have unit length are known as partial grid graphs. Their recognition is NP-hard already in very restricted cases. However, the moderate number of machines in practical instances suggests the use of exact algorithms that may even enumerate the possible layouts to choose from. We start with an elementary $n^{O(\sqrt{n})}$ time algorithm, but then we argue that even simpler exponential branching algorithms are more usable for practical sizes $n$, although being asymptotically worse. One algorithm interpolates between obvious $O^*(3^n)$ time and $O^*(4^{\nu})$ time for graphs with many small connected components. It can be modified in order to accommodate also a limited number of edges that can exceed unit length. Next we show that connected graphs have at most $2.9241^n$ grid layouts that can also be efficiently enumerated. An $O^*(2.6458^n)$ time branching algorithm solves the recognition problem, or yields a succinct enumeration of layouts with some surcharge on the time bound. In terms of the grid size we get a slightly better $O^*(2.6208^{\nu})$ time bound. Moreover, if we can identify a subgraph that is rigid, i.e., admits only one layout up to congruence, then all possible layouts of the entire graph are extensions of this unique layout, such that the combinatorial explosion is then confined to the rest of the graph. Therefore we also propose heuristic methods for finding certain types of large rigid subgraphs. The formulations of these results is more technical, however, the proposed method iteratively generates certain rigid subgraphs from smaller ones.