Planar Topological Inference (Algorithms and Theory of Computing)
Zhizhong Chen, Michelangelo Grigni, Christos H. Papadimitriou · Institutional Repositories DataBase (IRDB) · 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 preliminary properties of such graphs, and give a poly- nomial 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.