On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
Michael R. Fellows, Michael Allen Langston · SIAM Journal on Discrete Mathematics · 1992
The existence of decision algorithms with low-degree polynomial running times for a number of well-studied graph layout, placement, and routing problems is nonconstructively proved. Some were not previously known to be in $\mathcal{P}$ at all; others were only known to be in $\mathcal{P}$ by way of brute force or dynamic programming formulations with unboundedly high-degree polynomial running times. The methods applied include the recent Robertson–Seymour theorems on the well-partial-ordering of graphs under both the minor and immersion orders. The complexity of search versions of these problems is also briefly addressed.