Map Graphs

Details Map Graphs Map Graphs

1999-10-13

arxiv.org/abs/cs/9910013v1

Computer Science

Discrete Mathematics

46 pages, LaTeX with 41 PS figures; see http://www.mathcs.emory.edu/~mic/mapgraphs/ for hi-res figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Map Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Map Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Map Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105795