A graph is chordal (or triangulated) if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes.

## Arguments

- graph
The input graph. It may be directed, but edge directions are ignored, as the algorithm is defined for undirected graphs.

- alpha
Numeric vector, the maximal chardinality ordering of the vertices. If it is

`NULL`

, then it is automatically calculated by calling`max_cardinality()`

, or from`alpham1`

if that is given..- alpham1
Numeric vector, the inverse of

`alpha`

. If it is`NULL`

, then it is automatically calculated by calling`max_cardinality()`

, or from`alpha`

.- fillin
Logical scalar, whether to calculate the fill-in edges.

- newgraph
Logical scalar, whether to calculate the triangulated graph.

## Value

A list with three members:

- chordal
Logical scalar, it is

`TRUE`

iff the input graph is chordal.- fillin
If requested, then a numeric vector giving the fill-in edges.

`NULL`

otherwise.- newgraph
If requested, then the triangulated graph, an

`igraph`

object.`NULL`

otherwise.

## Details

The chordality of the graph is decided by first performing maximum
cardinality search on it (if the `alpha`

and `alpham1`

arguments
are `NULL`

), and then calculating the set of fill-in edges.

The set of fill-in edges is empty if and only if the graph is chordal.

It is also true that adding the fill-in edges to the graph makes it chordal.

## References

Robert E Tarjan and Mihalis Yannakakis. (1984). Simple
linear-time algorithms to test chordality of graphs, test acyclicity of
hypergraphs, and selectively reduce acyclic hypergraphs. *SIAM Journal
of Computation* 13, 566–579.

## See also

Other chordal:
`max_cardinality()`

## Author

Gabor Csardi csardi.gabor@gmail.com

## Examples

```
## The examples from the Tarjan-Yannakakis paper
g1 <- graph_from_literal(
A - B:C:I, B - A:C:D, C - A:B:E:H, D - B:E:F,
E - C:D:F:H, F - D:E:G, G - F:H, H - C:E:G:I,
I - A:H
)
max_cardinality(g1)
#> $alpha
#> [1] 9 4 6 8 3 5 7 2 1
#>
#> $alpham1
#> + 9/9 vertices, named, from 6a5bad9:
#> [1] G F D B E C H I A
#>
is_chordal(g1, fillin = TRUE)
#> $chordal
#> [1] FALSE
#>
#> $fillin
#> [1] 2 6 8 7 5 7 2 7 6 1 7 1
#>
#> $newgraph
#> NULL
#>
g2 <- graph_from_literal(
A - B:E, B - A:E:F:D, C - E:D:G, D - B:F:E:C:G,
E - A:B:C:D:F, F - B:D:E, G - C:D:H:I, H - G:I:J,
I - G:H:J, J - H:I
)
max_cardinality(g2)
#> $alpha
#> [1] 10 8 9 6 7 5 4 2 3 1
#>
#> $alpham1
#> + 10/10 vertices, named, from 22d96f8:
#> [1] J H I G C F D B E A
#>
is_chordal(g2, fillin = TRUE)
#> $chordal
#> [1] TRUE
#>
#> $fillin
#> numeric(0)
#>
#> $newgraph
#> NULL
#>
```