AMS 301 Chapter Notes - Chapter 1.1: Planar Graph, Aph Technological Consulting, Regions Of France
28 Feb 2021
School
Department
Course
Professor
Document Summary
A graph is planar if it can be drawn on a piece of paper w/o any edges crossing. The redrawing as a plane graph shows the planarity. Two approaches on determining if a graph is planar. The first approach involves a systematic method for trying to draw a graph edge-by-edge with no crossing edges. the second approach develops some theory with a goal of finding properties of planar graph. useful. We want to use the fewest colors possible to color countries in a map such that countries with a common border get different colors. Make a dual graph of the map graph with a vertex for each country and an edge joining adjacent countries. Now the map coloring problem becomes a vertex coloring problem, with adjacent vertices different colors. Challenge; how to determine whether a graph is planar. First find a circuit that visits all the vertices and draw the circuit in a large circle; and then.
