# Improved and More Realistic Algorithms for Maximal Graph Connectivity

We study the maximal connectivity problem (MCP), which is defined as follows: Given a set V of n vertices and a set E of m pairwise disjoint edge pairs, we define a family G(V, E) as the set of multigraphs that have vertex set V and contain exactly one edge from every pair in E. We want to find a multigraph in G(V, E) that has the minimal number of connected components. We present an O(nm)-time algorithm for this problem. Our result is obtained by avoiding the explicit construction of the auxiliary graph of [21] and querying only the relevant parts of the graph when needed. Our second result studies graph families G(V, E) that are derived from a surface simplification problem described in [8]. This problem was the initial motivation for studying MCP. The edge pairs in these families are non-disjoint; but their structure is restricted enough to allow an efficient solution of MCP on these families. In particular, the NP-hardness proof for MCP on general families G(V, E) such that the edge pairs in E are non-disjoint does not apply.

Attachment | Size |
---|---|

CS-2004-04.pdf | 483.82 KB |