An Application of Algebraic Topology to an Overlay Problem of Analytical Cartography
Alan Saalfeld · Cartography and Geographic Information Systems · 1991
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 n ∑j=1 i r(Ai∪Aj). (3)