# An Application of Algebraic Topology to an Overlay Problem of Analytical Cartography

Author: Saalfeld, Alan

Source: Cartography and Geographic Information Science, 1 January 1991, vol. 18, no. 1, pp. 23-36(14)

Publisher:

The full text article is temporarily unavailable.

We apologise for the inconvenience. Please try again later.

Abstract:

The number of elementary connected regions arising from overlaying two or more map layers may be computed directly from the connectivity of the line graphs of the two or more layers and from the connectivity of the intersection graph(s) of those line graphs. We find formulas for that number and use those formulas to establish upper bounds on the number of regions in an overlay. The Mayer-Vietoris homology sequence for simplicial complexes: … → Hi(A∩B) → Hi(A) ⊕ Hi(B) → Hi(A∪B) →i Hi−1(A∩B) → … is the tool we borrow from algebraic topology. We use exactness of the Mayer-Vietoris sequence to derive our principal result: For any plane graph X, let r(X) be the number of regions of the plane separated by X. Then r(X) is the number of connected components in the planar complement of X; r(X) is also one more than the maximum number of independent cycles in the graph X; and r(X) is easily computed using standard graph traversal techniques on X for counting independent cycles. Let c(X) be the number of connected components of X. If A and B are plane graphs to be overlaid, then A∪B is the plane graph of the overlay; and we have

r(A∪B) = r(A) + r(B) − r(A∩B) + c(A∩B) − c(A) − c(B) + c(A∪B), and     (1)

r(A∪B) ≤ r(A) + r(B) + c(A∩B).    (2)

Finally, we use mathematical induction on inequality (2) to show that for map layers whose line networks are connected, the number of regions arising from multiple overlays is never more than the sum of regions produced by taking pairwise overlays:

r(i=1 n∪ Ai)≤∑i=1 nj=1 i r(Ai∪Aj).    (3)

Document Type: Research Article

Publication date: January 1, 1991

Related content

#### Key

Free content
New content
Open access content
Subscribed content
Free trial content

A | A | A | A