We consider the following two problems. (i) Given a graph, add a minimum size clique to the graph such that the resulting graph is 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.
Bibtex entry:
@techreport{egres-05-04,
AUTHOR | = | {Fekete, Zsolt}, |
TITLE | = | {Source location with rigidity and tree packing requirements}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2005}, |
NUMBER | = | {TR-2005-04} |