PHD
  1. Algebra  1.1. Group Theory  1.1.1. Basic Properties of Groups  1.1.2. Subgroups  1.1.3. Cosets and Lagrange's Theorem  1.1.4. Normal Subgroups  1.1.5. Quotient Groups  1.1.6. Group Homomorphisms  1.1.7. Sylow Theorems  1.1.8. Free Groups  1.1.9. Group Actions  1.1.10. Simple and Solvable Groups  1.2. Ring Theory  1.2.1. Rings and Ideals  1.2.2. Ring Homomorphisms  1.2.3. Polynomial Rings  1.2.4. Principal Ideal Domains  1.2.5. Unique Factorization Domains  1.2.6. Noetherian Rings  1.2.7. Artinian Rings  1.3. Field Theory  1.3.1. Field Extensions  1.3.2. Splitting Fields  1.3.3. Galois Theory  1.3.4. Algebraic Closures  1.3.5. Finite Fields  1.3.6. Transcendental Extensions  1.4. Module Theory  1.4.1. Modules over Rings  1.4.2. Free Modules  1.4.3. Module Homomorphisms  1.4.4. Simple and Semi-Simple Modules  1.4.5. Projective Modules  1.4.6. Injective Modules  1.5. Linear Algebra  1.5.1. Vector Spaces  1.5.2. Linear Transformations  1.5.3. Eigenvalues and Eigenvectors  1.5.4. Canonical Forms  1.5.5. Inner Product Spaces  1.5.6. Spectral Theorem  1.5.7. Singular Value Decomposition
  2. Analysis  2.1. Real Analysis  2.1.1. Real Numbers and Completeness  2.1.2. Sequences and Series  2.1.3. Continuity  2.1.4. Differentiation  2.1.5. Riemann Integration  2.1.6. Metric Spaces  2.1.7. Lebesgue Measure  2.2. Complex Analysis  2.2.1. Complex Numbers  2.2.2. Analytic Functions  2.2.3. Contour Integration  2.2.4. Cauchy's Theorem  2.2.5. Residue Theorem  2.2.6. Conformal Mappings  2.3. Functional Analysis  2.3.1. Normed Spaces  2.3.2. Banach Spaces  2.3.3. Hilbert Spaces  2.3.4. Linear Operators  2.3.5. Spectral Theory  2.3.6. Compact Operators  2.4. Measure Theory  2.4.1. Sigma Algebras  2.4.2. Measures and Integrals  2.4.3. Lebesgue Integration  2.4.4. Convergence Theorems  2.4.5. Fubini's Theorem  2.5. Harmonic Analysis  2.5.1. Fourier Series  2.5.2. Fourier Transforms  2.5.3. Distribution Theory  2.5.4. Wavelets
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Continuity  3.1.3. Compactness  3.1.4. Connectedness  3.1.5. Metric Topology  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy Theory  3.2.3. Homology Theory  3.2.4. Cohomology  3.2.5. Exact Sequences  3.3. Differential Topology  3.3.1. Smooth Manifolds  3.3.2. Tangent Spaces  3.3.3. Vector Fields  3.3.4. Differential Forms
  4. Geometry  4.1. Differential Geometry  4.1.1. Curves and Surfaces  4.1.2. Riemannian Geometry  4.1.3. Geodesics  4.1.4. Curvature  4.2. Algebraic Geometry  4.2.1. Affine and Projective Varieties  4.2.2. Schemes  4.2.3. Divisors and Intersections  4.2.4. Cohomology in Algebraic Geometry  4.3. Computational Geometry  4.3.1. Convex Hulls  4.3.2. Triangulations  4.3.3. Voronoi Diagrams  4.3.4. Geometric Algorithms
  5. Number Theory  5.1. Elementary Number Theory  5.1.1. Divisibility  5.1.2. Congruences  5.1.3. Modular Arithmetic  5.2. Analytic Number Theory  5.2.1. Prime Number Theorem  5.2.2. Dirichlet Series  5.2.3. Zeta and L-functions  5.3. Algebraic Number Theory  5.3.1. Number Fields  5.3.2. Ideals  5.3.3. Class Groups  5.3.4. Galois Representations
  6. Combinatorics  6.1. Enumerative Combinatorics  6.1.1. Generating Functions  6.1.2. Recurrence Relations  6.1.3. Permutations and Combinations  6.2. Graph Theory  6.2.1. Graph Isomorphisms  6.2.2. Planarity  6.2.3. Graph Coloring  6.3. Extremal Combinatorics  6.3.1. Ramsey Theory  6.3.2. Probabilistic Methods in Extremal Combinatorics  6.4. Algebraic Combinatorics  6.4.1. Matrix Methods  6.4.2. Representation Theory
  7. Logic and Foundations  7.1. Set Theory  7.1.1. Zermelo-Fraenkel Axioms  7.1.2. Ordinals and Cardinals  7.2. Model Theory  7.2.1. Structures and Theories in Model Theory  7.2.2. Compactness Theorem  7.3. Proof Theory  7.3.1. Formal Systems  7.3.2. Consistency and Completeness
  8. Probability and Statistics  8.1. Probability Theory  8.1.1. Random Variables  8.1.2. Expectation and Variance  8.1.3. Central Limit Theorem  8.2. Stochastic Processes  8.2.1. Markov Chains  8.2.2. Brownian Motion  8.3. Statistical Inference  8.3.1. Hypothesis Testing  8.3.2. Regression Analysis
  9. Applied Mathematics  9.1. Numerical Analysis  9.1.1. Iterative Methods  9.1.2. Interpolation  9.1.3. Error Analysis  9.2. Partial Differential Equations  9.2.1. Elliptic Equations  9.2.2. Parabolic Equations  9.2.3. Hyperbolic Equations  9.3. Dynamical Systems  9.3.1. Chaos Theory  9.3.2. Stability Analysis in Dynamical Systems

PHD → Combinatorics → Graph Theory ↓


Planarity


In graph theory, planarity is a fascinating topic that deals with embedding a graph in a plane. When a graph can be drawn on a flat surface without any edges crossing each other, it is called a planar graph. This property makes planar graphs quite interesting, used in various fields such as computer science, geography, and engineering. In this article, we will dive deep into the concept of planarity, exploring definitions, tools, and examples to understand it better.

Basic definitions

To fully understand flatness, let's first establish some basic definitions.

Graph

A graph G is defined as a collection of vertices V and edges E, where each edge connects a pair of vertices. Formally, it is expressed as G = (V, E).

Planar graphs

A graph is considered planar if it can be drawn on the plane without crossing any edge. This drawing is called a plane embedding of the graph.

Face

In a planar graph, a face is a region enclosed by edges. The face covering the outer region of a planar graph is called an unbounded face or outer face.

Euler's formula

Euler's formula gives a specific condition for a connected planar graph, stating:

V – E + F = 2

where V is the number of vertices, E is the number of edges, and F is the number of faces. This equation is important in identifying and analyzing planar structures.

Examples of planar graphs

Let's consider some examples to understand what planar graphs look like. A standard example is a simple polygon.

K4 graphs

K4 is a complete graph with four vertices. It is always planar, no matter how it is drawn.

Cycle C3 graph

An even simpler example is the triangle graph C3, which is always planar.

Flatness test

Determining whether a graph is planar involves checking whether it can be reconstructed in a way that avoids edge crossings. There are algorithms specifically for this purpose, and here we discuss some basic tests.

Kuratowski theorem

Kuratowski's theorem provides simple information about planarity. It states that a graph is non-planar if, and only if, it contains a subgraph that is a subpartition of K_5 (the complete graph with five vertices) or K_{3,3} (the complete bipartite graph).

Wagner's theorem

Similar to Kuratowski's theorem, Wagner's theorem provides a criterion for the graph not having a cycle minor (the minor is obtained by deleting or compressing edges) that contains K_5 or K_{3,3}.

Applications of planar graphs

Planar graphs appear in a variety of real-world contexts, providing insight into fields such as computer science, geography, and engineering. Here are some notable examples:

VLSI Design: In circuit design, planar graphs are used to arrange components on silicon chips in a way that minimizes the distances between conductor paths, optimizes space, and increases performance.

Geographic Mapping: Maps are widely used in geographic studies to display data effectively without any overlap, allowing for clear and understandable visualizations.

Network Design: Designing networks such as paths, roads, or even telecommunication lines involves ensuring minimum overlap to avoid signal interference and optimize flow. Planar graphs play a very important role in designing such optimal routes.

Generating planar graphs

Creating a planar graph involves strategic vertex configuration. In practice, this may mean repeatedly checking for crossing edges and re-placing them until no crossings exist.

Step-by-step example

Consider transforming a non-planar graph into a planar form using iterative repositioning of edges.

  1. Start with a crossed structure.
  2. Identify and mark intersecting edges.
  3. Modify the vertices to eliminate intersections.
  4. Continue this approach until all interconnections are eliminated.
  5. Evaluate the complete planar graph.

Conclusion

Understanding planarity is important in many domains, where explicit and crossing-free representations are essential. Planar graphs play a vital role not only in theoretical mathematics but also in practical applications affecting everyday infrastructure. By studying detailed definitions and examples along with real-world applications, we gain a deeper understanding of how planarity affects structures in our lives and how it simplifies complex problems through the power of visualization and explicit representation.


PHD → 6.2.2


U
username
0%
completed in PHD

← Prev (6.2.1)
Graph Isomorphisms
Next (6.2.3) →
Graph Coloring

Comments 



Planarity

https://www.buddymath.com/phd/6.2.2?bmal=en