Graph Layout Problems

Sergio Cavero (), Eduardo G. Pardo (), Abraham Duarte () and Rafael Martí ()
Additional contact information
Sergio Cavero: Universidad Rey Juan Carlos, Departamento de Informática y Estadística
Eduardo G. Pardo: Universidad Rey Juan Carlos, Departamento de Informática y Estadística
Abraham Duarte: Universidad Rey Juan Carlos, Department of Computer Science and Statistics
Rafael Martí: University of Valencia, Operations Research and Statistics Department, School of Mathematics

Chapter 42 in Handbook of Heuristics, 2025, pp 1321-1351 from Springer

Abstract: 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.

Keywords: Embedding; Graph layout; Heuristics; Cutwidth; Bandwidth; Optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-032-00385-0_45

Ordering information: This item can be ordered from
http://www.springer.com/9783032003850

DOI: 10.1007/978-3-032-00385-0_45

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().