ABSTRACT
The study of planar graphs is motivated by the famous Four Color Problem. Can the regions of any map on the globe be colored with four colors so that regions sharing a nontrivial boundary have different colors? Recently, the study of circuit layouts on silicon chips provides another motivation for such a study. Crossings cause problems in a layout. We want to know which circuits have layouts without crossings. Recently, the study of planar graphs is generalized into topological graph theory: layout graphs on different surfaces.
