Layout

Layout --- укладка, нумерация.

A layout (or linear layout, linear arrangement) of a graph [math]\displaystyle{ G = (V,E) }[/math] is an assignment of distinct integers from [math]\displaystyle{ \{1, \ldots, n\} }[/math] to the elements of [math]\displaystyle{ V }[/math]. Equivalently, a layout [math]\displaystyle{ {\mathcal L} }[/math] may be thought of as an ordering [math]\displaystyle{ {\mathcal L}(1), }[/math] [math]\displaystyle{ \ldots, }[/math] [math]\displaystyle{ {\mathcal L}(n) }[/math] of [math]\displaystyle{ V }[/math], where [math]\displaystyle{ |V| = n }[/math]. A tree layout is a linear arrangement of a tree. If [math]\displaystyle{ p }[/math] is a non-integer point on [math]\displaystyle{ x }[/math]-axis, then the cut of the layout [math]\displaystyle{ {\mathcal L} }[/math] at [math]\displaystyle{ p }[/math], denoted [math]\displaystyle{ cut_{{\mathcal L}}(p) }[/math] is the number of edges that cross over [math]\displaystyle{ p }[/math], i.e. the number of edges [math]\displaystyle{ (u,v) \in G }[/math] with [math]\displaystyle{ {\mathcal L}(u) \lt p \lt {\mathcal L}(v) }[/math]. The cutwidth of a layout [math]\displaystyle{ {\mathcal L} }[/math], denoted [math]\displaystyle{ cut({\mathcal L}) }[/math], is the maximum cut of [math]\displaystyle{ {\mathcal L} }[/math] over all possible values; namely,

[math]\displaystyle{ cut({\mathcal L}) = \max_{1 \lt p \lt |V|} cut_{{\mathcal L}}(p). }[/math]

The cutwidth of a graph [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ cut(G) }[/math], is the minimum cutwidth of any linear arrangement of [math]\displaystyle{ G }[/math].

The width of a layout [math]\displaystyle{ {\mathcal L} }[/math], [math]\displaystyle{ b(G,{\mathcal L}) }[/math], is the maximum of [math]\displaystyle{ |{\mathcal L}(u) - {\mathcal L}(v)| }[/math] over all edges [math]\displaystyle{ (u,v) }[/math] of [math]\displaystyle{ G }[/math]. That is, it is the length of the longest edge in the layout. The bandwidth of [math]\displaystyle{ G }[/math], [math]\displaystyle{ bw(G) }[/math], is the minimum width over all layouts. A bandwidth layout for a graph [math]\displaystyle{ G }[/math] is a layout satisfying [math]\displaystyle{ b(G,{\mathcal L}) = bw(G) }[/math].

See also

• Bandwidth, Separation-width.