  The problem of finding the maximum-weight, planar subgraph of a finite,
simple graph with nonnegative real edge weights is well known in industrial and
electrical engineering, systems biology, sociology and finance. As the problem
is known to be NP-hard, much research effort has been devoted over the years to
attempt to improve a given approximate solution to the problem by using local
moves applied to a planar embedding of the solution. It has long been
established that any feasible solution to the problem, a maximal planar graph,
can be transformed into any other (having the same vertex set) in a finite
sequence of local moves of based on: (i) edge substitution and (ii) vertex
relocation and it has been conjectured that moves of only type (i) are
sufficient. In this note we settle this conjecture in the affirmative.
Furthermore, contrary to recent supposition, we demonstrate that any maximal
spanning tree of the original graph is not necessarily a part of any optimal
solution to the problem. We hope these results will be useful in the design of
future approximate methods for the problem.
