Necessary edges in k-chordalisations of graphs

H.L. Bodlaender

Research output: Contribution to journalArticleAcademicpeer-review

14 Citations (Scopus)


A k-chordalisation of a graph G = (V, E) is a graph H = (V, F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V, E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G?. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If A is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.
Original languageEnglish
Pages (from-to)283-290
Number of pages8
JournalJournal of Combinatorial Optimization
Issue number3
Publication statusPublished - Sept 2003
Externally publishedYes


  • Chordal graphs
  • Graph algorithms
  • Interval graphs
  • Pathwidth
  • Treewidth
  • Triangulated graphs


Dive into the research topics of 'Necessary edges in k-chordalisations of graphs'. Together they form a unique fingerprint.

Cite this