Problem Description

Currently SageMath lacks a method to generate random graphs with fixed treewidth. Both k-trees and partial k-trees offer a practical solution to generate such graphs and can be produced with simple algorithms.

Proposed Solution

I've started working on algorithms which produce generate these random graphs. K-tree generation consists of first generating a complete graph, and then randomly creating a new clique of k+1 vertices as each new vertex is added to the graph.

Alternatives Considered

As far as I've seen there aren't any ways to generate graphs with fixed treewidth or graphs which are otherwise similar to k-trees within SageMath.

Additional Information

No response

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.