Computer Science – Data Structures and Algorithms
Scientific paper
2010-06-17
Theoretical Computer Science, 412(22):2370-2379, 2011
Computer Science
Data Structures and Algorithms
Scientific paper
10.1016/j.tcs.2011.01.018
Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a number of graph classes for which the problem is polynomial, even trivial. A natural step, outstanding thus far, was to provide a broad classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of allowed vertex degrees in the input graphs, yielding a full dichotomy on the complexity of the problem. As byproducts, the previous NP-completeness result for binary trees was strengthened to strictly binary trees, and the three-dimensional version of the problem was for the first time proven to be NP-complete. Our results were made possible by introducing the concepts of consistent orientations and robust gadgets, and by showing how the former allows NP-completeness proofs by local replacement even in the absence of the latter.
da Fonseca Guilherme D.
de Figueiredo Celina M. H.
de Sá Vinícius G. P.
Machado Raphael
No associations
LandOfFree
Complexity dichotomy on partial grid recognition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity dichotomy on partial grid recognition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity dichotomy on partial grid recognition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-552736