Map Graphs in Polynomial Time

Z. Chen et al. (1997, 1998) have introduced a modified notion of planarity, where two faces are considered adjacent if they share at least one point. The corresponding abstract graphs are called map graphs. Chen et al. raised the question of whether map graphs can be recognized in polynomial time. They showed that the decision problem is in NP and presented a polynomial time algorithm for the special case where we allow at most 4 faces to intersect in any point-for only 3 are allowed to intersect in a point, we get the usual planar graphs. Chen et al. conjectured that map graphs can be recognized in polynomial time, and in this paper, their conjecture is settled affirmatively.

Authors

• Mikkel Thorup

Keywords

• Polynomials
• History
• Computer science
• Lapping
• Face recognition
• Functional Graph
• Graphs In Polynomial Time
• Conjecture
• Planar Graphs
• Graph Abstraction
• Intersection Point
• Local Problems
• Linear Order
• Cluster A
• Recursive Algorithm
• Original Graph
• Corner Points
• Closed Curve
• Split Point
• Set Of Faces
• Mapping Problem
• Single Face
• Inner Nodes
• Single Bubble