What is Tree-depth?

In graph theory, the tree-depth of a connected undirected graph G {\displaystyle G} is a numerical invariant of G {\displaystyle G} , the minimum height of a Trémaux tree for a supergraph of G {\displaystyle G}. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.