|
Treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called '' -trees'', and the graphs with treewidth at most are called '' partial -trees''. Many other well-studied graph families also have bounded treewidth. Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other. Treewidth is commonly used as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tree Decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. The concept of tree decomposition was originally introduced by . Later it was rediscovered by and has since been studied by many other authors. Definition Intuitively, a tree decomposition represents the vertices of a given graph as subtrees of a tree, in such a way that vertices in are adjacent only when the corresponding subtrees intersect. Thus, forms a subgraph of the intersection graph of the subtrees. The full intersection graph is a chordal graph. Each subtree associates a graph vertex with a set of tree nodes. To define this formally, we represent each ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bramble (graph Theory)
In graph theory, a bramble for an undirected graph is a family of connected subgraphs of that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in that has one endpoint in each subgraph. The ''order'' of a bramble is the smallest size of a hitting set, a set of vertices of that has a nonempty intersection with each of the subgraphs. Brambles may be used to characterize the treewidth of .. In this reference, brambles are called "screens" and their order is called "thickness". Treewidth and havens A haven of order ''k'' in a graph ''G'' is a function ''β'' that maps each set ''X'' of fewer than ''k'' vertices to a connected component of ''G'' − ''X'', in such a way that every two subsets ''β''(''X'') and ''β''(''Y'') touch each other. Thus, the set of images of ''β'' forms a bramble in ''G'', with order ''k''. Conversely, every bramble may be used to determine a haven: for each set ''X'' of size smaller ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Haven (graph Theory)
In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit–evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs... Definition If is an undirected graph, and is a set of vertices, then an -flap is a nonempty connected component of the subgraph of formed by deleting . A haven of order in is a function that assigns an -flap to every set of fewer than vertices. This function must also satisfy additional constraints which are given differently by different authors. The number is called the ''order'' of the haven.. In the original ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Partial K-tree
In graph theory, a partial ''k''-tree is a type of graph, defined either as a subgraph of a ''k''-tree or as a graph with treewidth at most ''k''. Many NP-hard combinatorial problems on graphs are solvable in polynomial time when restricted to the partial ''k''-trees, for bounded values of ''k''. Graph minors For any fixed constant ''k'', the partial ''k''-trees are closed under the operation of graph minors, and therefore, by the Robertson–Seymour theorem, this family can be characterized in terms of a finite set of forbidden minors. The partial 1-trees are exactly the forests, and their single forbidden minor is a triangle. For the partial 2-trees the single forbidden minor is the complete graph on four vertices. However, the number of forbidden minors increases for larger values of ''k''. For partial 3-trees there are four forbidden minors: the complete graph on five vertices, the octahedral graph with six vertices, the eight-vertex Wagner graph, and the pentagona ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chordal Completion
In graph theory, a branch of mathematics, a chordal completion of a given undirected graph is a chordal graph, on the same vertex set, that has as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible. A different type of chordal completion, one that minimizes the size of the maximum clique in the resulting chordal graph, can be used to define the treewidth of . Chordal completions can also be used to characterize several other graph classes including AT-free graphs, claw-free AT-free graphs, and cographs. The minimum chordal completion was one of twelve computational problems whose complexity was listed as open in the 1979 book ''Computers and Intractability''. Applications of chordal completion include modeling the problem of minimizing fill-in when performing Gaussian elimination on sparse symmet ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Halin Graph
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross (this is called planar embedding), and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.''Encyclopaedia of Mathematics'', first Supplementary volume, 1988, , p. 281, articl"Halin Graph" and references therein. Halin graphs are named after German mathematician Rudolf Halin, who studied them in 1971.. The cubic Halin graphs – the ones in which each vertex touches exactly three edges – had already been studied over a century earlier by Kirkman. Halin graphs are polyhedral graphs, meaning that every Halin graph can be used to form the vertices and edges of a convex polyhedron, and the polyhedra formed from th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chordal Graph
In 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. They are sometimes also called rigid circuit graphs. or triangulated graphs.. Chordal graphs are a subset of the perfect graphs. They may be recognized in linear time, and several problems that are hard on other classes of graphs such as graph coloring may be solved in polynomial time when the input is chordal. The treewidth of an arbitrary graph may be characterized by the size of the cliques in the chordal graphs that contain it. Perfect elimination and efficient recogn ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Apollonian Network
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction. Definition An Apollonian network may be formed, starting from a single triangle embedded in the Euclidean plane, by repeatedly selecting a triangular face of the embedding, adding a new vertex inside the face, and connecting the new vertex to each vertex of the face containing it. In this way, the triangle containing the new vertex is subdivided into three smaller triangles, which may in turn be subdivided in the same way. Examples The complete graphs on three and four vertices, and , are both Apollonian networks. is formed by starting with a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Series–parallel Graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and terminology In this context, the term graph means multigraph. There are several ways to define series–parallel graphs. The following definition basically follows the one used by David Eppstein. A two-terminal graph (TTG) is a graph with two distinguished vertices, ''s'' and ''t'' called ''source'' and ''sink'', respectively. The parallel composition ''Pc = Pc(X,Y)'' of two TTGs ''X'' and ''Y'' is a TTG created from the disjoint union of graphs ''X'' and ''Y'' by merging the sources of ''X'' and ''Y'' to create the source of ''Pc'' and merging the sinks of ''X'' and ''Y'' to create the sink of ''Pc''. The series composition ''Sc = Sc(X,Y)'' of two TTGs ''X'' and ''Y'' is a TTG created from the disjoint union of graphs ''X'' and ''Y' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-tree
In graph theory, a ''k''-tree is an undirected graph formed by starting with a (''k'' + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex ''v'' has exactly ''k'' neighbors ''U'' such that, together, the ''k'' + 1 vertices formed by ''v'' and ''U'' form a clique. Characterizations The ''k''-trees are exactly the maximal graphs with a treewidth of ''k'' ("maximal" means that no more edges can be added without increasing their treewidth). They are also exactly the chordal graphs all of whose maximal cliques are the same size ''k'' + 1 and all of whose minimal clique separators are also all the same size ''k''.. Related graph classes 1-trees are the same as unrooted trees. 2-trees are maximal series–parallel graphs, and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks. The graphs that have treewidth at most ''k'' are exactly the subgraphs of ''k''-trees ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Outerplanar Graph
In 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 and , 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. The outerplanar graphs are a subset of the planar graphs, the subgraphs of series–parallel graphs, and the circle graphs. The maximal outerplanar graphs, those to which no more edges can be added while preserving outerplanarity, are also chordal graphs and visibility graphs. History Outerplanar graphs were first studied and named by , in connection with the problem of determining the planarity of graphs formed by using a perfect matching to conn ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
