Checking if a Graph is Planar - v, e & f

  • Thread starter kljoki
  • Start date
  • Tags
    Graph
In summary, the conversation discusses determining if a given graph is planar by using the formula v - e + f = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces. It is mentioned that the graph in question has 9 vertices and 15 edges, resulting in 8 faces. The question then arises about an efficient method for counting faces on a graph, with the suggestion of starting at a specific point and compiling a list of connections. Another approach suggested is to check for the presence of specific subgraphs.
  • #1
kljoki
5
0
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
 
Physics news on Phys.org
  • #2
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
kljoki said:
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...
 

1. What is a planar graph?

A planar graph is a type of mathematical graph in which the edges do not intersect each other when drawn on a two-dimensional surface. This means that it can be drawn on a piece of paper without any overlapping edges or vertices.

2. How do you determine if a graph is planar?

To determine if a graph is planar, you can use the Euler's formula which states that for a connected planar graph, v - e + f = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces. If this equation holds true for the graph, then it is planar.

3. What is the maximum number of edges in a planar graph?

The maximum number of edges in a planar graph is 3v - 6, where v is the number of vertices. This is known as the Euler's inequality and it helps in determining if a graph is planar or not. If the number of edges in a graph exceeds this maximum value, then the graph is not planar.

4. Can a non-planar graph be converted to a planar graph by adding or removing edges?

No, a non-planar graph cannot be converted to a planar graph by adding or removing edges. In fact, adding or removing edges can sometimes make a graph non-planar. The structure of the graph, including the number of vertices and edges, determines if it is planar or not.

5. Are all planar graphs connected?

No, not all planar graphs are connected. A connected graph is one in which there is a path between every pair of vertices. A planar graph can have disconnected components, but the individual components must still be planar.

Similar threads

Replies
1
Views
920
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
932
Replies
4
Views
861
  • STEM Educators and Teaching
Replies
5
Views
613
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Replies
3
Views
642
  • Introductory Physics Homework Help
Replies
1
Views
425
  • Set Theory, Logic, Probability, Statistics
Replies
22
Views
1K
Back
Top