Graph Layout Problems

Abstract

The term layout problem was introduced in the context of Very Large-Scale Integration (VLSI) circuit design. Their main objective is to project an original graph onto a predefined host graph with a well-known topology, such as a path, cycle, or grid graph, among others. In this chapter, we review the five most relevant graph layout problems: the Cutwidth, the Minimum Linear Arrangement, the Vertex Separation, the SumCut, and the Bandwidth. Each problem is presented with its formal definition, and it is illustrated with a detailed example. Additionally, we describe their state-of-the-art heuristic methods and the instances used in their evaluation. Since graph layouts represent a challenge for optimization methods in general and for heuristics in particular, this review pays special attention to strategies and methodologies that provide high-quality solutions.