INTR ODU CTIO N
Graph theory is regarde d as one of the areas of applied mathem atics.
Eulers is known as " Father of Graph theory". Subseq uent develop ments have been
made by kirchho ff, cayley, Hamiltt on etc . The discove ries had their roots in the
Physica l World. In the past few years Graph theory has been establis hed as an
inporta nt mathem atical roots in wide variety of subjects .
The study or planar and non planar graphs how contrib uted a great deal
to the growth of graph theory. The Planarit y of graphs is great signific ance from the
theoreti cal points of view. Planari ty and other related concep ts are useful in many
,
practic al situatio ns . The importa nt charact erizatio n theorem s for planar graph
namely , kuratow ski ~s theorem and Whitne y's theorem are present ed.
The dissert ation consist s of three chapter s. In the first chapte r
In
contain s the basis definiti ons and results which are needs in subsequ ent chapter s.
second chapter , propert ies of Planar graph are discuss ed some necessa ry and
sufficie~,t conditi ons for graphs to be planar are conside red. The Euler's formula and
its corolla ries are also include d in this chapter.
In the last chapter we constru ct what is known as the geomet ric dual of
. g •apJ order to provide some intuitiv e motivat ion for the concept of
· p Iana1 1 1,
•
a given 111
duality in graph theory to be explained
, CH AP TE R -1
PR EL IM IN A R IE S
are included.
In this chapter some basic definitions and results
Definition 1.1.1
V ,V ...... .. } called
A graph G = (V,E) consists of set of objects V={ 1 2
se elements are called edges such
vertices and another set E ={ e 1,e 2...... ... } who
(V V of vertices. The vertices
that edge ek is identified with an unordered pair
• )
1 1
of ek.
V;, V a~sociated with edge ek are called end vertices
1
. ii
means of a diagram
The most common representation of a graph is by
edge as a line segmentjoining its
in which the vertices are represented as points and
end vertices.
Exa mp lel.1 .2
G is a graph with 5 vertices and 8 edges .
, 2
D ef in iti on 1. 1.3
A edge having the sam
e vertex as both its end ve
rtices is called a loop . In
graph q..given above eRis in a loop.
D ef in iti on 1.1.4
If more than one edges
are assiciated with a give
n pair of vertice s th
ose
edges are called paralle
l edges or multiple edge
s. In the above graph e
4 an d e 5 are
multiple edges.
De fin iti on 1.1.5
The graph that has neith
er loops nor parallel ed
ges is called a simpl e
D ef in iti on 1.1.6
A graph having no edge
s is called null graph or em
pty graph.
D ef in iti on 1.1. 7
.
A cornplete graph 1s .
a s11np 1e grap h m
· i · 'h c::ich r
w 111c air of di sti nct
·
vertices is jo ined by an
edge.
Graph theory is regarde d as one of the areas of applied mathem atics.
Eulers is known as " Father of Graph theory". Subseq uent develop ments have been
made by kirchho ff, cayley, Hamiltt on etc . The discove ries had their roots in the
Physica l World. In the past few years Graph theory has been establis hed as an
inporta nt mathem atical roots in wide variety of subjects .
The study or planar and non planar graphs how contrib uted a great deal
to the growth of graph theory. The Planarit y of graphs is great signific ance from the
theoreti cal points of view. Planari ty and other related concep ts are useful in many
,
practic al situatio ns . The importa nt charact erizatio n theorem s for planar graph
namely , kuratow ski ~s theorem and Whitne y's theorem are present ed.
The dissert ation consist s of three chapter s. In the first chapte r
In
contain s the basis definiti ons and results which are needs in subsequ ent chapter s.
second chapter , propert ies of Planar graph are discuss ed some necessa ry and
sufficie~,t conditi ons for graphs to be planar are conside red. The Euler's formula and
its corolla ries are also include d in this chapter.
In the last chapter we constru ct what is known as the geomet ric dual of
. g •apJ order to provide some intuitiv e motivat ion for the concept of
· p Iana1 1 1,
•
a given 111
duality in graph theory to be explained
, CH AP TE R -1
PR EL IM IN A R IE S
are included.
In this chapter some basic definitions and results
Definition 1.1.1
V ,V ...... .. } called
A graph G = (V,E) consists of set of objects V={ 1 2
se elements are called edges such
vertices and another set E ={ e 1,e 2...... ... } who
(V V of vertices. The vertices
that edge ek is identified with an unordered pair
• )
1 1
of ek.
V;, V a~sociated with edge ek are called end vertices
1
. ii
means of a diagram
The most common representation of a graph is by
edge as a line segmentjoining its
in which the vertices are represented as points and
end vertices.
Exa mp lel.1 .2
G is a graph with 5 vertices and 8 edges .
, 2
D ef in iti on 1. 1.3
A edge having the sam
e vertex as both its end ve
rtices is called a loop . In
graph q..given above eRis in a loop.
D ef in iti on 1.1.4
If more than one edges
are assiciated with a give
n pair of vertice s th
ose
edges are called paralle
l edges or multiple edge
s. In the above graph e
4 an d e 5 are
multiple edges.
De fin iti on 1.1.5
The graph that has neith
er loops nor parallel ed
ges is called a simpl e
D ef in iti on 1.1.6
A graph having no edge
s is called null graph or em
pty graph.
D ef in iti on 1.1. 7
.
A cornplete graph 1s .
a s11np 1e grap h m
· i · 'h c::ich r
w 111c air of di sti nct
·
vertices is jo ined by an
edge.
