Let G Γ
(V, E) be a graph where V and E are a set of nodes and a set of edges, respectively. Let X Γ
{V 1 , V 2 , . . . , V p }, V i β V be a family of node-subsets. Each node-subset V i is called an area, and a pair of G and X is called an area graph. A node Β£ β V and an area V i β X are called k-NA (nodeto-area)-connected if the minimum size of a cut separating Β£ and V i is at least k. We say that an area graph ( G, X ) is k-NA-edge-connected when each Β£ β V and V i β X are k-NA-edge-connected. This paper gives a necessary and sufficient condition for a given ( G, X ) to be k-NA-edge-connected: ( G, X ) is k-NA-edge-connected iff, for all positive integers h Β°k, every h-edge-connected component of G includes at least one node from each area or has at least k edges between the component and the rest of the nodes. This paper also studied the Minimum Area Augmentation Problem, i.e., the problem of determining whether or not a given area graph ( G, X ) is k-NA-edge-connected and of choosing the minimum number of nodes to be included in appropriate areas to make the area graph k-NA-edgeconnected (if ( G, X ) is not k-NA-edge-connected). This problem can be regarded as one of the location problems, which arises from allocating service-nodes on multimedia networks. We propose an O(ΓEΓ / ΓVΓ 2 / L / min{ΓEΓ, kΓVΓ}min{ kΓVΓ, k / ΓVΓ 2 }) time algorithm for solving this problem, where L is a space required to represent output areas. For a fixed k, this algorithm also runs in linear time when the h-edge-connected components of G are available for all h Γ
1, 2, . . . , k.