Separator-Decomposition Ta of G(V,E): each node iE TG corresponds to (Vi,Si) Vroot such that ∫Voot=V and Vieaf=0 Si0 is a vertex separator ofV,CVi in G[V闭 OVi is vertex boundary of Vi in G[Vi] 2 width:max{S,oV} i∈Tc separator-width sw(G): width of optimal TG Theorem: sw(G)=Θ(tw(G)and TG can be constructed 0 0 in time poly(n).20(tw(G))￾ ￾ width: Separator-Decomposition of TG G(V,E): separator-width sw(G) : UI` i￾TG {|Si|, |￾Vi|} width of optimal TG each node i ￾ TG corresponds to (Vi, Si) VZWW\ = V ￾Vi is vertex boundary of Vi in G[Vi] is a vertex separator of in Si ￾= ￾ Vj , Vk ￾ Vi G[Vi] VZWW\ = V and VTMIN = ￾ ￾ such that sw(G) = ￾(tw(G)) in time XWTa(n) · 2O(tw(G)) TG Theorem: and can be constructed Vi Vj S Vk i Vj Vk ￾Vi