Planar map graphs
Zhi‐Zhong Chen, Enory Grigni, Christos H. Papadimitriou · 1998
We introduce and study a modified notion of planarity, in which two regions of a map are considered adjacent when they share any point of their boundaries (not an edge, as standard planarity requires).We seek to characterize the abstract graphs realized by such map adjacencies.We prove some preliiinary properGs of such graphs, and give a polynomial time algorithm for the following restricted problem: given an abstract graph, decide whether it is realized by a map in which at most four regions meet at any point.The general recognition problem remains open. 1 Introduction 1.1 Motivation: Topological Inference Suppose that you are told t.hat four planar regions relate in the following way: A is inside B; B overlaps G; C touches D on t.he outside; D overlaps B; D is disjoint from A; and C overlaps A. All four planar regions are "bubbles" with no holes (to be rigorous: disc homeomorphs).Is this possible?If so, we would like a model, a picture of four regions so related; if not, a proof of impossibility.This deceptively simple estension of propositional logic is known as the topological inference problem [5], and its special cases, extensions, and variants are studied in the area of geographic information systems [3, 4, 10, 5, 111.Despite much effort (and claims in t.he literature [12, 41.. .),no decision algorithm and f&rite asiomatization for this problem is known -although t,he problem becomes both finitely axiomatizable and polynomial-time decidable in any number of dimensions ot,her than two.In fact, the following special