Skip to main content
`Ctrl`+`K`

# complete_to_chordal_graph

complete_to_chordal_graph(G)

  Return a copy of G completed to a chordal graph

  Adds edges to a copy of G to create a chordal graph. A graph G=(V,E) is called chordal if for each cycle with length bigger than 3, there exist two non-adjacent nodes connected by an edge (called a chord).

  Parameters:
    G NetworkX graph

      Undirected graph

  Returns:
    H NetworkX graph

      The chordal enhancement of G

    alpha Dictionary

      The elimination ordering of nodes of G

  Notes

  There are different approaches to calculate the chordal enhancement of a graph. The algorithm used here is called MCS-M and gives at least minimal (local) triangulation of graph. Note that this triangulation is not necessarily a global minimum.

  https://en.wikipedia.org/wiki/Chordal_graph

  References

  [1]

  Berry, Anne & Blair, Jean & Heggernes, Pinar & Peyton, Barry. (2004) Maximum Cardinality Search for Computing Minimal Triangulations of Graphs. Algorithmica. 39. 287-298. 10.1007/s00453-004-1084-3.

  Examples

      >>> from networkx.algorithms.chordal import complete_to_chordal_graph
      >>> G = nx.wheel_graph(10)
      >>> H, alpha = complete_to_chordal_graph(G)