Graphs of Maps

Details Graphs of Maps Graphs of Maps

2003-05-03

arxiv.org/abs/math/0305058v1

Mathematics

Combinatorics

131 pages, 29 Figures. This is my PhD Thesis presented to the University of Waterloo, 1980

Scientific paper

This work studies certain aspects of graphs embedded on surfaces. Initially, a colored graph model for a map of a graph on a surface is developed. Then, a concept analogous to (and extending) planar graph is introduced in the same spirit as planar abstract duality, and is characterized topologically. An extension of the Gauss code problem treating together the cases in which the surface involved is the plane or the real projective plane is established. The problem of finding a minimum transversal of orientation-reversing circuits in graphs on arbitrary surfaces is proved to be NP-complete and is algorithmically solved for the special case where the surface is the real projective plane.

Affiliated with

Also associated with

No associations

Rating

Graphs of Maps 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 Graphs of Maps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphs of Maps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-154633