Skip to main content

Posts

Showing posts with the label Planar

Graph Theory: Planar Graphs

Continuing from the previous post ( which is  here  ). This is a bit short post. I think this post is not at all helpful in olys but then let's do it cause I find them interesting :P. Here are my notes.. Book referred: Daniel A Marcus Graph theory Chapter H: Planar Graphs: A planar graph is a graph that can be represented by a diagram with no edge cross. Such a diagram is called a plane diagram. For $K_4$ is a planar graph. Regions formed by a graph:  The planar graph divides the plan into regions  Non- planar graph: A non-planar graph is a graph that always has a edge cross.  Regional Degrees: The regions are boundaries by edges. The number od edges each region is boundaries with is called regional degrees. Subdivision: A graph that is obtained by inserting vertices of degree $2$ is an already existing edge. Regional Degree theorem: Let $G$ be a connected graph and let $r_1,r_2,\dots $ be the degrees of the regions in any plane diagram of $G.$ Then the sum o...