Planar Planar and Non-planar graphsand Non-planar graphs

planar and non planar

1. Planar and Non-planar graphs Presented by: Supervisor: Snarya S. Hussein Dr. Didar A. Ali Fatma M. Ahmed

2. Outline Definition Note Example Theorem (Euler’s Formula) Example Theorem Corollary Example Definition References

3. Definition A graph is planar if it can be drawn so that its edges do not cross.

4. Note The Path Graph of order n is a planar graph for all The Cycle Graph of order n is a planar graph for all The wheel Graph of order n is a planar graph for all The star Graph of order n is a planar graph for all The complete Graph of order n is a planar graph for all The complete bipartite graph is planar if either 𝑚 = 1 or 𝑛 = 1 also 𝐾2,2. The graph 𝐾3,3 is a non-planar graph.  

5. Definition Bounded regions defined by planar graphs are called faces (regions), but unbound region called exterior face.

6. Example This graph has a total of three faces: f = 3 Two interior faces (A, B) One exterior face (C)

7. Theorem: Euler Formula If 𝐺 is a connected plane graph, then In the above theorem or formula, , , and denote the number of vertices, edges, and faces of the graph G respectively.  

8. A connected planar graph has 5 vertices and 7 edges, How many faces dose the graph have? Solution: Euler’s Formula So number of faces is 4.   Example.

9. Theorem: For any planar graph in which every face is then, Example: Does there exists a planar graph of order 18, and each face is 𝐶 5, if exists construct it, and then find the number of faces. Solution: If the graph exists, then must satisfy the equation. Which is not integer, therefore the graph does not exists.  

10. Corollary If G is any (𝑝, 𝑞) planar graph with 𝑝 ≥ 3, then 𝑞 ≤ 3𝑝 − 6, if G has no triangle, then 𝑞 ≤ 2𝑝 – 4

11. Is K5 is a planar graph? Solution: if K5 is planar graph, then must satisfies the inequality Sine 10 is not less or equal to 9 is not planar graph.   Example 1.

12. Is K3,3 is a planar graph? Solution: is K3,3 is a planar graph then must satisfies the inequality is not planar graph   Example 2.

13. Definition A maximal planar graph is a graph in which no edge can be added without losing planarity. Example: the graphs 𝐾3,3 − 𝑒 and 𝐾5 − 𝑒 are maximal planar graphs.

14. References Tutte, W. T. (1956). A theorem on planar graphs. Transactions of the American Mathematical Society. Whitney, H. (1933). Planar graphs. In Hassler Whitney Collected Papers. Boston, MA: Birkhäuser Boston. Biedl, T., Liotta, G., & Montecchiani , F. (2015). On visibility representations of non-planar graphs.