Complexity dichotomy on partial grid recognition
type: Item
instance of: scholarly article
title: Complexity dichotomy on partial grid recognition
zbMATH Open document ID: 1211.68214
author: Guilherme D. Da Fonseca
author: Vinícius G. P. De Sá
author: R. C. S. Machado
author: Celina M. H. de Figueiredo
published in: Theoretical Computer Science
publication date: 2011-05-10T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 5886217
zbMATH Keywords: graph embedding
zbMATH Keywords: VLSI layout
zbMATH Keywords: partial grid
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.01.018
OpenAlex ID: W1983471422
cites work: The complexity of minimizing wire lengths in VLSI layouts
cites work: The total chromatic number of some bipartite graphs
cites work: Q3154375
cites work: The realization problem for Euclidean minimum spanning trees is NP-hard
cites work: The logic engine and the realization problem for nearest neighbor graphs
cites work: Unit-length embedding of binary trees on a square grid
cites work: Expansion of layouts of complete binary trees into grids
cites work: Q3326832
DOI: 10.1016/J.TCS.2011.01.018
description: scientific article; zbMATH DE number 5886217