OUTERPLANAR GRAPH Meaning and
Definition
-
An outerplanar graph is a type of graph that can be embedded in the plane in such a way that all of its vertices are placed on the outer boundary, i.e., the boundary of a convex region. These graphs have a special property where there exists a planar drawing of the graph such that no two edges intersect except at their endpoints.
To better understand the concept, "outerplanar" refers to the fact that all the vertices of the graph lie on the outer side or periphery of a convex region. This convex region can be visualized as a closed shape, like a circle or polygon, and the graph is drawn within this boundary.
One important characteristic of outerplanar graphs is that they do not contain any subgraphs that can be regarded as graphs of two or more separate components. In simpler terms, there are no "holes" or enclosed regions within these graphs.
Outerplanar graphs are often used in various applications, such as network topology, geometric modeling, and graph theory. They have several interesting properties that make them suitable for specific types of algorithms and computational problems. For example, outerplanar graphs can be efficiently colored using a small number of colors, and they have a linear number of edges compared to the number of vertices.
Overall, an outerplanar graph is a graph that can be represented in a planar drawing with all its vertices on the outer boundary of a convex region, without any intersecting edges and without any holes or enclosed regions inside its structure.
Etymology of OUTERPLANAR GRAPH
The term "outerplanar graph" combines two components: "outer" and "planar".
The word "outer" comes from the Old English word "ūterra", which means "further out" or "exterior". In the context of graph theory, an outerplanar graph is a graph that can be embedded in a plane with all its vertices and edges located on the outer face (the boundary).
The word "planar" comes from the Latin word "planus", meaning "flat" or "level". In graph theory, a planar graph is a graph that can be drawn without any edges crossing each other when drawn on a flat surface (usually a plane).
By combining these two terms, the word "outerplanar" describes a graph that is both planar and has its vertices and edges on the outer boundary when embedded on a surface.
