| Article ID: | iaor20073053 |
| Country: | Netherlands |
| Volume: | 34 |
| Issue: | 6 |
| Start Page Number: | 607 |
| End Page Number: | 612 |
| Publication Date: | Nov 2006 |
| Journal: | Operations Research Letters |
| Authors: | Fekete Zsolt |
We consider the following two problems: (i) given a graph, find a minimum size vertex-set such that the pinning of it makes the graph rigid in the plane. (ii) Given a graph, contract a minimum size vertex-set such that the resulting graph has two edge-disjoint spanning trees. We prove that these problems are polynomially solvable.