NIELIT 2017 July Scientist B (CS) - Section B: 15

Question

Choose the most appropriate definition of plane graph.

• A. A simple graph which is isomorphic to hamiltonian graph.
• B. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset $X$ and $Y$ in such a way that each edge of $G$ has one end in $X$ and one end in $Y$.
• C. A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices.
• D. None of the option.

Answer 1

Option C is the Correct Answer.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other.Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Definition 1 : A graph G(V, E) is called plane if

                      • V is a set of points in the plane;

                      • E is a set of curves in the plane such that

                          1. every curve contains at most two vertices and these vertices are the ends of the curve;

                          2. the intersection of every two curves is either empty, or one, or two vertices of the graph.

Definition 2 : A graph is called planar, if it is isomorphic to a plane graph. The plane graph which is isomorphic to a given planar graph G is said to be embedded in the plane. A plane graph isomorphic to G is called its drawing.

Answer 2

 

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph.