Layout of planar products

Abstract

Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such a way that a certain objective function is optimized. In this paper, planar direct products and their stack and queue layouts are determined. The stack and queue numbers are directly motivated by VLSI layout problems.