Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00541
Enumerating Grid Layouts of Graphs
Peter Damaschke
Vol. 24, no. 3, pp. 433-460, 2020. Regular paper.
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.
|
Submitted: August 2019.
Accepted: July 2020.
Final: August 2020.
Published: August 2020.
Communicated by
Antonios Symvonis
|
Journal Supporters
|