Map Graphs
| dc.creator | Chen, Zhi-Zhong | |
| dc.creator | Grigni, Michelangelo | |
| dc.creator | Papadimitriou, Christos | |
| dc.date | 1999-10-13 | |
| dc.date.accessioned | 2026-07-07T03:24:24Z | |
| dc.date.available | 2026-07-07T03:24:24Z | |
| dc.description | We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires). Such adjacencies define a map graph. We give an NP characterization for such graphs, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point. | |
| dc.description | 46 pages, LaTeX with 41 PS figures; see http://www.mathcs.emory.edu/~mic/mapgraphs/ for hi-res figures | |
| dc.identifier | https://arxiv.org/abs/cs/9910013 | |
| dc.identifier | http://arxiv.org/abs/cs/9910013 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33312 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | G.2.2; F.2.2 | |
| dc.title | Map Graphs | |
| dc.type | text |