.1October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.DrawingPlanar GraphsMathematics for Computer ScienceMIT 6.042J/18.062J.2October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar GraphsA graph is planar if thereis a way to draw it in the plane without edges crossing..3October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar GraphsMaps are 2-connected planar graphs.4October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.General connected planar graphs may havePlanar GraphsMaps are 2-connected planar graphs.5October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.General connected planar graphs may havedonglesPlanar GraphsMaps are 2-connected planar graphs.6October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.General connected planar graphs may havedonglesPlanar Graphscross barsMaps are 2-connected planar graphs.7October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.A Planar Graph.8October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.A Planar Graph123with 3 faces.9October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.A Planar Graph123123with 3 faces.10October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.A Planar Graph1234123(wait! also the outer face)with 3 faces.11October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.A Planar Graph12341234(wait! also the outer face)with 3 faces4.12October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Drawing a Planar Graphdraw it edge by edge,starting with a single vertex.13October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Drawing a Planar Graphdraw it edge by edge,starting with a single vertexgraph.14October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.and record faces while drawinggraphDrawing a Planar Graph.15October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.facesand record faces while drawinggraphDrawing a Planar Graph.16October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsfacesand record faces while drawinggraph.17October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsfacesand record faces while drawinggraph.18October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsfacesand record faces while drawinggraph.19October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsfacesand record faces while drawinggraph.20October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsand record faces while drawinggraph(the outer face)faces.21October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsand record faces while drawinggraph(the outer face)faces.22October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsand record faces while drawinggraph(the outer face)faces.23October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsand record faces while drawinggraph(the outer face)faces.24October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsand record faces while drawinggraph(the outer face)faces.25October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Planar Graphsand record faces while drawinggraph(the outer face)faces.26October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Recursive Definition of FacesPrecise rules defining the cycles that are the face boundaries of a Planar Drawing:.27October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Start with a vertexRecursive Definition of Faces.28October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Start with a vertexThere is one face, whose boundary is the 0-length cycle consisting of this vertex.Recursive Definition of Faces.29October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Two cases for connected graph:1) Attach edge from vertex on a face to a new vertex.2) Attach edge between nonadjacent vertices on a face.Recursively adding an edge to a drawing.30October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.1) choose vertex, v, on a face boundaryFace Creation Rule 1.31October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.1) choose vertex, v, on a face boundaryvFace Creation Rule 1.32October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.1) choose vertex, v, on a face boundaryvpath xFace Creation Rule 1.33October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.1) choose vertex, v, on a face boundaryvface boundary vxvpath xFace Creation Rule 1.34October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.1) choose vertex, v, on a face boundaryvwCreate new vertex, w,Face Creation Rule 1.35October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.1) choose vertex, v, on a face boundaryvCreate new vertex, w,and add edge v--wwFace Creation Rule 1.36October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.vwold face boundary vxvpath xFace Creation Rule 1.37October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvFace Creation Rule 1path xnew face boundary.38October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvFace Creation Rule 1path xnew face boundary.39October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvFace Creation Rule 1path xnew face boundary vwvxv.40October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Face Creation Rulesnothing else changesnew face boundary vwvxv.41October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.Recursive Face Creation Rule 22) choose vertices v, w on a face boundary.42October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.v2) choose vertices v, w on a face boundarywFace Creation Rule 2.43October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.v2) choose vertices v, w on a face boundarywFace Creation Rule 2with v, w, not adjacent.44October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.wvFace Creation Rule 2xyface boundary vywxv2) choose vertices v, w on a face boundary.45October 8, 2005Copyright © Albert R. Meyer, 2005. All rights reserved.vFace Creation Rule 22) choose vertices v, w on a face
View Full Document
Unlocking...