Editing Chordal graph (section)

==Chordal completions and treewidth==
{{main|Chordal completion}}
If {{mvar|G}} is an arbitrary graph, a '''chordal completion''' of {{mvar|G}} (or '''minimum fill-in''') is a chordal graph that contains {{mvar|G}} as a subgraph. The parameterized version of minimum fill-in is [[Parameterized complexity|fixed parameter tractable]], and moreover, is solvable in parameterized subexponential time.{{sfnp|Kaplan|Shamir|Tarjan|1999}}{{sfnp|Fomin|Villanger|2013}}  
The [[treewidth]] of {{mvar|G}} is one less than the number of vertices in a [[maximum clique]] of a chordal completion chosen to minimize this clique size.
The [[k-tree|{{mvar|k}}-trees]] are the graphs to which no additional edges can be added without increasing their treewidth to a number larger than&nbsp;{{mvar|k}}.
Therefore, the {{mvar|k}}-trees are their own chordal completions, and form a subclass of the chordal graphs. Chordal completions can also be used to characterize several other related classes of graphs.{{sfnp|Parra|Scheffler|1997}}