Treewidth di grafici a griglia quadrati kxk

Question

Secondo alcune diapositive Ho trovato su Google, la treewidth di qualsiasi $ k tempi k $ Grafico a griglia quadrata $ G $ è $ tw (g) = k $. Ho appena iniziato a ricercare la treewidth e la decomposizione degli alberi, e per la maggior parte ha senso. Tuttavia, sono particolarmente interessato al caso grafico a griglia quadrata $ K Times K $, ma ho avuto difficoltà a come è possibile effettuare una decomposizione dell'albero di un tale grafico con quel minimo di una larghezza.

Uno dei problemi in cui incontro quando cerco di eliminare gli alberi di decomposizione di piccole griglie quadrate con gruppi di più $ k+1 $ (per garantire un albero di decomposizione in cui la larghezza è $ k $) è che poiché il grafico è "ciclico ", Uno dei nodi d'angolo si presenta in due estremità opposte dell'albero, ma non in nessun nodi sul percorso tra i due. Ciò viola chiaramente la proprietà di coerenza degli alberi di decomposizione, che secondo Wikipedia (che dà una definizione più precisa della maggior parte) è:

If $ x_ {i} $, $ x_ {j} $ e $ x_ {k} $ sono nodi (nell'albero di decomposizione) e $ x_ {k} $ è sul percorso da $ x_ {i} $ a $ X_ {j} $, quindi $ x_ {i} cap x_ {j} sottomarino x_ {k} $.

Per il caso del grafico $ 3 tempi 3 $, l'unico albero di decomposizione valido (o almeno quello che credo sia valido) che riesco a pensare contiene 2 nodi: $ { {1, 2, 3, 4, 6 , 7, 8, 9 }, {2, 4, 5, 6, 8 } } $ in cui i nodi sono etichettati per riga a partire dall'angolo in alto a sinistra:

$ 1 Space2 Space3 $

$ 4 Space5 Space6 $

$ 7 Space8 Space9 $

L'ho fatto prendendo i vertici perimetrali per il primo nodo dell'albero e il vertice interno ($ 5 $) insieme ai suoi vertici adiacenti per garantire che tutti i bordi e i vertici siano inclusi.

Alla fine, la mia domanda è: come può la treewidth di un grafico a griglia quadrata $ k temp - tims k $ a $ k $? E se questo è corretto, potresti presentare/spiegare un semplice esempio di un albero di decomposizione che dimostra questa proprietà?