Dual graphIn the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e.
Planar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
Outerplanar graphIn graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants. They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2.
Graph minorIn graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.
Planar separator theoremIn graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of O(\sqrt{n}) vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.
PlanarizationIn the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph. Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial vertex, causing each crossed edge to be subdivided into a path. The original graph will be represented as an immersion minor of its planarization.
Line graphIn the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.
Planarity testingIn graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal.
Chordal graphIn the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.
Slope stabilitySlope stability refers to the condition of inclined soil or rock slopes to withstand or undergo movement; the opposite condition is called slope instability or slope failure. The stability condition of slopes is a subject of study and research in soil mechanics, geotechnical engineering and engineering geology. Analyses are generally aimed at understanding the causes of an occurred slope failure, or the factors that can potentially trigger a slope movement, resulting in a landslide, as well as at preventing the initiation of such movement, slowing it down or arresting it through mitigation countermeasures.
