In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a partial ''k''-tree is a type of graph, defined either as a subgraph of a
''k''-tree or as a graph with
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 gr ...
at most ''k''. Many
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
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 minor
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...
s, and therefore, by the
Robertson–Seymour theorem
In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that i ...
, this family can be characterized in terms of a finite set of
forbidden minor
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...
s. The partial 1-trees are exactly the
forests
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
, and their single forbidden minor is a triangle.
For the partial 2-trees the single forbidden minor is the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...
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
In the mathematical field of graph theory, the Wagner graph is a 3- regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.
Properties
As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one ...
, and the
pentagonal prism with ten vertices.
[.]
Dynamic programming
Many algorithmic problems that are
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
for arbitrary graphs may be solved efficiently for partial ''k''-trees by
dynamic programming, using the
tree decompositions of these graphs.
Related families of graphs
If a family of graphs has bounded
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 gr ...
, then it is a subfamily of the partial ''k''-trees, where ''k'' is the bound on the treewidth.
Families of graphs with this property include the
cactus graph
In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ...
s,
pseudoforest
In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. Tha ...
s,
series–parallel graphs,
outerplanar graphs,
Halin graphs, and
Apollonian networks.
For instance, the series–parallel graphs are a subfamily of the partial 2-trees, and more strongly a graph is a partial 2-tree if and only if each of its
biconnected components is series–parallel.
The
control-flow graph
In computer science, a control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution. The control-flow graph was discovered by Frances E. Allen, who noted tha ...
s arising in the
compilation of
structured programs also have bounded treewidth, which allows certain tasks such as
register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocat ...
to be performed efficiently on them.
[.]
Notes
References
*.
*.
*.
*.
*.
{{refend
Graph families
Graph minor theory