Complexity dichotomy on partial grid recognition

DOI10.1016/j.tcs.2011.01.018zbMath1211.68214OpenAlexW1983471422MaRDI QIDQ533881

Guilherme Dias da Fonseca, Celina M. Herrera de Figueiredo, Raphael C. S. Machado, Vinícius G. Pereira de Sá

Publication date: 10 May 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.01.018

zbMATH Keywords

NP-completenessgraph embeddingVLSI layoutpartial grid

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Enumerating Grid Layouts of Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of minimizing wire lengths in VLSI layouts
• Unit-length embedding of binary trees on a square grid
• The logic engine and the realization problem for nearest neighbor graphs
• Expansion of layouts of complete binary trees into grids
• The realization problem for Euclidean minimum spanning trees is NP-hard
• The total chromatic number of some bipartite graphs

This page was built for publication: Complexity dichotomy on partial grid recognition