@misc{KosterWolleBodlaender, author = {Koster, Arie M.C.A. and Wolle, Thomas and Bodlaender, Hans L.}, title = {Degree-Based Treewidth Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8193}, number = {04-44}, abstract = {Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgra ph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds.}, language = {en} }