Map graphs

ABSTRACT

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, derive some consequences regarding sparsity and coloring, and survey some algorithmic results.

REFERENCES

• 1: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 2: Borodin, O. V. 1984. Solution of Ringel's problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs. Metody Diskret. Analiz. 41, 12--26. In Russian.
• 3: Oleg V. Borodin, Cyclic coloring of plane graphs, Discrete Mathematics, v.100 n.1-3, p.281-289, May 15, 1992 [doi>10.1016/0012-365X(92)90647-X]
• 4: Oleg V. Borodin, A new proof of the 6 color theorem, Journal of Graph Theory, v.19 n.4, p.507-521, July 1995 [doi>10.1002/jgt.3190190406]
• 5: Zhi-Zhong Chen, Approximation algorithms for independent sets in map graphs, Journal of Algorithms, v.41 n.1, p.20-40, October 2001 [doi>10.1006/jagm.2001.1178]
• 6: Zhi-Zhong Chen , Enory Grigni , Christos H. Papadimitriou, Planar map graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.514-523, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276865]
• 7: Chen, Z.-Z., Grigni, M., and Papadimitriou, C. 1999. Map graphs. Manuscript, arXiv:cs.DM/ 9910013, 46 pages.
• 8: Zhi-Zhong Chen , Xin He, Hierarchical Topological Inference on Planar Disc Maps, Proceedings of the 6th Annual International Conference on Computing and Combinatorics, p.115-125, July 26-28, 2000
• 9: Zhi-Zhong Chen , Xin He , Ming-Yang Kao, Nonplanar topological inference and political-map graphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.195-204, January 17-19, 1999, Baltimore, Maryland, United States
• 10: Ehrlich, G., Even, S., and Tarjan, R. E. 1976. Intersection graphs of curves in the plane. J. Combinat. Theory Ser. B 21, 1, 8--20.
• 11: Grigni, M., Papadias, D., and Papadimitriou, C. 1995. Topological inference. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI, Inc., Somerset, N.J., pp. 901--907.
• 12: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 13: Jan Kratochvíl, String graphs. II.: Recognizing string graphs is NP-hard, Journal of Combinatorial Theory Series B, v.52 n.1, p.67-78, May 1991 [doi>10.1016/0095-8956(91)90091-W]
• 14: Ore, O., and Plummer, M. D. 1969. Cyclic coloration of plane graphs. In Recent Progress in Combinatorics (Proceedings of the 3rd Waterloo Conference on Combinatorics, 1968). Academic Press, New York, pp. 287--293.
• 15: Renz, J. 1998. A canonical model of the region connection calculus. In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning. Morgan-Kaufmann, San Francisco, Calif., pp. 330--341.
• 16: Marcus Schaefer , Eric Sedgwick , Daniel Štefankovič, Recognizing string graphs in NP, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509910]
• 17: Marcus Schaefer , Daniel Stefankovic, Decidability of string graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.241-246, July 2001, Hersonissos, Greece [doi>10.1145/380752.380807]
• 18: Mikkel Thorup, Map Graphs In Polynomial Time, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.396, November 08-11, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Map graphs, maps, topological inference