Clique Representations and Dimension-\(k\) Chordal Graphs

The well-known clique tree representation for chordal graphs is extended to multidimensional representations for arbitrary graphs in which the number of vertices in the representation, minus the number of edges, plus the number of distinguished cycles, minus the number of distinguished polyhedra, and so on, always equals one. This approach generalizes both chordal graphs and cycle spaces of graphs. It also leads to a `dimension’ parameter that is shown to be no greater than the boxicity, chromatic number, and tree-width parameters.