Properties of Optimum Subgraphs

In this section we establish a fundamental property of optimum subgraphs for MPWPSP. This helps to reduce the search space of planar subgraphs which may be candidates for an optimum solution. The property also serves as the basis for the heuristics to be described in the next section.

Observation 1. Any maximal planar subgraph of K_n is a maximal planar graph with 3n-6 edges.
Theorem 1. Let G=(V,E) have nonnegative edge weights. Then there is an optimum solution to MPWPSP for G which is a triangulation.
Proof: The input is a complete graph G=K_n, n=|V|, with $w(u,v) \ge 0$ for all $uv \in E_G$. Hence, G has a planar subgraph with 3n-6 edges which is a triangulation. Now suppose an optimum subgraph H has less than 3n-6 edges. Without loss of generality, assume H has 3n-7 edges. Since H is not maximal planar, there is a maximal planar subgraph M of G such that $M = H \cup {e}$ for some $e=uv \in E_G$, $e \not\in E_{H}$. Furthermore, M has 3n-6 edges and is a triangulation. Now d_M(u,v)=1 and $d_{H}(u,v) \ge 2$. Hence, P_w(M) > P_w(H), since adding an edge to H cannot decrease its proximity weight and M has the same proximity weight as H only if w(u,v)=0. Thus, it follows that M is an optimum solution.
 

1998-12-21