Scribd Logo
Upload

Welcome to Scribd!

  • 243 views

    Planner Graph

    Uploaded by

    FahimAbrar
    The document provides information about planar graphs including definitions and properties. A planar graph is one that can be drawn without edge intersections except at vertices. Non-planar graphs like K5 and K3,3 are discussed. Euler's formula relating vertices, edges and faces is proved. Maximum and planar graphs as well as dual graphs are also covered.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Planner Graph

    Uploaded by

    FahimAbrar
    243 views10 pages
    The document provides information about planar graphs including definitions and properties. A planar graph is one that can be drawn without edge intersections except at vertices. Non-planar graphs like K5 and K3,3 are discussed. Euler's formula relating vertices, edges and faces is proved. Maximum and planar graphs as well as dual graphs are also covered.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides information about planar graphs including definitions and properties. A planar graph is one that can be drawn without edge intersections except at vertices. Non-planar graphs like K5 and K3,3 are discussed. Euler's formula relating vertices, edges and faces is proved. Maximum and planar graphs as well as dual graphs are also covered.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    243 views10 pages

    Planner Graph

    Uploaded by

    FahimAbrar
    The document provides information about planar graphs including definitions and properties. A planar graph is one that can be drawn without edge intersections except at vertices. Non-planar graphs like K5 and K3,3 are discussed. Euler's formula relating vertices, edges and faces is proved. Maximum and planar graphs as well as dual graphs are also covered.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 10

    Lecture Notes On Planar Graphs

    Date of Lecture Hold: 29/04/2006

    Prepared By
    Mohammad Shamsul Aren
    Roll No: 100505002P
    M. Sc. In CSE
    Bangladesh University of Engineering & Technology
    (BUET)

    Planar Graphs
    Planar graph is a graph that can be drawn so that no edges intersect except at a vertex. For
    example, the following three graphs are planar.

    It is seen that rst graph above is already drawn as a planar graph. The second and third
    graphs are planar because they can be redrawn without intersecting edges except at vertices
    as follows:

    On the other hand, the two graphs shown below are not planar:

    In K5 , it is seen that edge e6 has been intersected with edges e8 and e9 , edge e7 has been
    intersected with edges e8 and e10 , edge e8 has been intersected with edges e6 and e7 , edge
    e9 has been intersected with edges e6 and e10 , e10 has been intersected with edges e7 and e9
    respectively. K5 can be redrawn in such a way that intersecting edges e8 and e9 will not
    2

    intersect any edges except at a vertex, but e10 will intersect with at least one edge except at a
    vertex. In any types of redrawing of K5 will have an edge that will intersect with other edge
    except at a vertex. So, from the denition of planar graph we can say that K5 is not a planar
    graph. Similarly, we will not able to draw k3,3 without an edge intersection except at a vertex.
    One possible redrawing of each of the graphs K5 and K3,3 are given below.

    From the gure above it is seen that K5 and K3,3 cannot be drawn without edge intersection
    of at least one edge. So, these two graphs are not planar. These two are the smallest
    non-planar graphs.

    Plane Graph
    A planar graph already drawn in the plane is called a plane graph or a planar map.We can
    also say that a plane graph is one that has been drawn in the plane in such a way that its
    edges intersect only at their common end-vertices. Following is a plane graph of K4 .

    Planar Embedding
    The dierent ways of drawing a planar graph in the plane is known as planar embedding.Consider the following two plane graphs:

    The above two plane graphs are the planar embeddings of the same planar graph.

    Concept of convex and non-convex objects


    An object is known as convex if any line joining any two points inside the object lie entirely
    inside the object. Otherwise the object will be known as non-convex object.
    The following objects are convex.

    The following objects are non-convex. The last one also shows why it is non-convex.

    Note:

    Graph of any 3D convex object is a 3-connected planar graph and vice versa.

    That is we can draw the graph of any 3D convex object without edge intersections except at
    vertices. The graph will also be a 3-connected means that to divide the drawn graph into two
    components we must have to delete 3 edges.
    Conversely, we shall be able to construct a 3D convex object from a 3-connected planar graph.
    4

    Denition of faces of a planar graph


    Let G be a plane graph, and consider the regions bounded by the edges of G. These regions
    are called faces of G.
    As for example the following graph has 7 faces (one of the face - the outside of the graph is
    usually called the innite face), 9 vertices and 14 edges.

    Euler's formula on planar graphs


    If G is a connected plane graph with n vertices, m edges and f faces, then

    - m + f =2.

    Proof: We can easily proof it by induction on m.


    Base Case: Suppose that m = 0. Then for G to be a connected graph, there may be only

    one vertex, and one face. So, n  m + f = 1  0 + 1 =2 and the formula works in the m = 0
    case.
    For the m = 1 case, there are 2 possibilities. First possibility is for the case of self-loop where
    there is only one vertex and second possibility is when there are two vertices joining them by
    an edge. In both cases, Euler's formula is valid as shown in the following gures.

    Inductive Case:

    For the inductive step, assuming that that m > 1 is given, and that the
    Euler formula works for all graphs with m - 1 edges.
    Now, if G is a tree, then f = 1 and m = n - 1. So, n  m + f = n  (n 1) + 1 = 2.
    If G is not a tree, then removing an edge e belonging to some circuit we nd a plane graph H
    on n vertices with m - 1 edge.
    Let,

    n H = the number of vertices of H


    m H = the number of edges of H
    f H = the number of faces of H
    Then, n H = n, m H = m - 1, and f H = f - 1. So,

    Thus, G satises the Euler's Formula.

    This completes the proof of the theorem.

    Corollary to Euler's theorem


    If G is a (connected) simple, nite planar graph with n vertices (n >= 3), then
    1. G has at most 3n - 6 edges.
    2. Furthermore, if G contains no triangles, then G has at most 2n - 4 edges.

    Proof (a):

    Suppose that G has at most m edges, consider some plane drawing of G, with f
    faces. Consider the number of pairs (e, F ) where e is one of the edges bounding the face F.

    For each edge e, there are at most 2 faces that it bounds. So, the total number of these edge
    face pairs has to be less than 2m. On the other hand, because G is a simple graph, each face
    is bounded by at least 3 edges. Therefore, the total number of edge-face pairs is greater than
    or equal to 3f. So, 3f =<2m
    By the Euler's Formula, n - m + f = 2, so, 3n - 3m + 3f = 6
    Since, 3f =< 2m, 3f = 6-3n + 3m 2m
    Re-arranging, m 3n 6
    This completes the proof of (a).

    Proof (b):

    If G has no triangles, each face must be bounded by 4 or more edges.

    So, like the previous one we get 4f 2m


    Or, 2f m
    From Euler's theorem we know,

    n  m + f =2
    => 2n  2m + 2f = 4
    => 2n 2m + m 4

    => m 2n - 4.
    This completes the proof of (b).

    Note:
    1. This corollary is true even for disconnected, simple, nite planar graphs, provided that
    each connected component has at least three vertices.
    2. This corollary is not a characterization for planar graphs.

    Edge Contractions
    Let u and v be the vertices of a graph G. Then removing the edge between u and v and
    considering u = v yields a new connected graph. Such type of operations on an edge of a
    graph is known as edge contractions.

    Kuratowski's Theorem
    A nite graph G is planar if and only if it contains no subgraph that is edge- contractible to
    K5 or K3,3 .

    Example:

    The Petersen graph may be represented pictorially as shown in the left gure
    below. With the help of edge contractions of dashed edges. We can convert it into complete
    graph K5 as shown in the right gure below. Since the Petersen graph is edge contractible to
    K5 , it is not a planar graph.

    A property of planar graph


    Every nite, simple, planar graph has a vertex of degree less than 6.

    Proof:

    Suppose that G is such a graph. Without loss of generality, G is connected. Suppose


    that G has n vertices, m edges, and that vertex j has degree d j (for 1 =< j =< n ). Then,

    Then, the average degree of the vertices of the graph G, is given by,
    Average Degree =<

    6n12
    n

    =6-

    12
    n

    <6

    So, at least one of the vertices has degree less than 6. This completes the proof of the corollary.

    Dual of a plane graph


    Suppose that G is a (nite) connected plane graph, then its dual G may be dened as follows:
    1. The faces of G will be considered as the vertices of G .
    2. For every pair of faces having an edge, e, in common, join the corresponding vertices in
    G by an edge that crosses the edge, e, only once.
    With the help of above two operations we will obtain the dual graph G of a connected graph.

    Example:

    In the following gure, the original plane graph is indicated with bold edges
    connecting its vertices and its dual is drawn with dashed edges connecting its vertices.

    Maximal and Maximum Planar graphs


    A simple planar graph is maximally planar if no edge can be added without violating its
    planarity. On the other hand a maximum planar graph is a simple planar graph where we can
    add new edges so that the graph remains a planar one. The graph in the left side below is a
    maximally planar whereas the graph on the right side is a maximum planar graph.

    Triangulation
    A triangulation is a simple plane graph where every face boundary is a 3-cycle.
    face excluding the outer face of a maximally planar is a triangulation.

    10

    Every

    You might also like