Separation-width

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

Given a layout [math]\displaystyle{ \varphi }[/math] of [math]\displaystyle{ G }[/math], [math]\displaystyle{ V_{\varphi}^{-}(i) }[/math], [math]\displaystyle{ V_{\varphi}^{+}(i) }[/math], and [math]\displaystyle{ V_{\varphi}^{\ast}(i) }[/math] are defined as follows:

[math]\displaystyle{ V_{\varphi}^{-}(i) = \{u \in V[E_{\varphi}(i)]: \varphi(u) \leq i\}, }[/math]

[math]\displaystyle{ V_{\varphi}^{+}(i) = \{v \in V[E_{\varphi}(i)]: i \lt \varphi(v)\}, }[/math]

[math]\displaystyle{ V_{\varphi}^{\ast}(i) = \left\{\begin{array}{l} V_{\varphi}^{-}(i)\mbox{ if }|V_{\varphi}^{-}(i)| \leq |V_{\varphi}^{+}(i)| \\ V_{\varphi}^{+}(i)\mbox{ otherwise.} \end{array} \right. }[/math]

Then we define the separation-width of [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ \varphi }[/math], denoted by [math]\displaystyle{ sw_{\varphi}(G) }[/math], by

[math]\displaystyle{ sw_{\varphi}(G) = \max \{|V_{\varphi}^{\ast}(i)|: 1 \leq i \leq |V|\}. }[/math]

We further define the separation-width [math]\displaystyle{ sw(G) }[/math] of [math]\displaystyle{ G }[/math] by

[math]\displaystyle{ sw(G) = \min_{\varphi} sw_{\varphi}(G), }[/math] where minimum is taken over all possible layouts of [math]\displaystyle{ G }[/math].