Planar graph check

  • Thread starter kljoki
  • Start date
  • #1
5
0

Main Question or Discussion Point

Hi
I have this graph
Drawing1 (2).jpg


now i should check if this graph can be planar.

v - number of vertices
e - number of edges
f - number of faces

to be planar it should hold v - e + f = 2 from here f = 2 - v + e = 2 - 9 + 15 = 8
so f = 8 now my question is how to easily count faces (regions bounded by edges, including the outer, infinitely large region) of the graph??
thanks
 

Answers and Replies

  • #2
11,687
5,257
couldnt you start with point a and then compile a list of connections that come back to a

a-b-e

a-b-f-i

and continue to point b, c, d ... making sure not to count the same loop again

as an example b-e-a is the same as a-b-e
 
  • #3
Bacle2
Science Advisor
1,089
10
Hi
I have this graph
View attachment 50059

now i should check if this graph can be planar.

v - number of vertices
e - number of edges
f - number of faces

to be planar it should hold v - e + f = 2 from here f = 2 - v + e = 2 - 9 + 15 = 8
so f = 8 now my question is how to easily count faces (regions bounded by edges, including the outer, infinitely large region) of the graph??
thanks
How about arguing that your graph contains neither a K3,3 nor a K5

as a subgraph? it seems there are not that many cases to consider...
 

Related Threads on Planar graph check

  • Last Post
Replies
2
Views
769
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
6
Views
3K
Replies
4
Views
3K
  • Last Post
Replies
8
Views
2K
Replies
3
Views
2K
Replies
2
Views
2K
Replies
13
Views
2K
Top