Separation-width

Separation-width --- ширина укладки.

Given a layout $\phi$ of $G$, $V_{\phi }^{-}(i)$, $V_{\phi }^{+}(i)$, and $V_{\phi }^{\ast }(i)$ are defined as follows:

$V_{\phi }^{-}(i)=\{u\in V[E_{\phi }(i)]:\phi (u)\le i\},$

$V_{\phi }^{+}(i)=\{v\in V[E_{\phi }(i)]:i<\phi (v)\},$

$V_{\phi }^{\ast }(i)=\{\begin{array}{l}{V}_{\phi }^{-}(i)\text{ if }|V_{\phi }^{-}(i)|\le |V_{\phi }^{+}(i)|\\ V_{\phi }^{+}(i)\text{ otherwise.}\end{array}$

Then we define the separation-width of $G$ with respect to $\phi$, denoted by $s{w}_{\phi }(G)$, by

$s{w}_{\phi }(G)=max\{|V_{\phi }^{\ast }(i)|:1\le i\le |V|\}.$

We further define the separation-width $sw(G)$ of $G$ by

$sw(G)=\underset{\phi }{min}s{w}_{\phi }(G),$ where minimum is taken over all possible layouts of $G$.