Layout --- укладка, нумерация.
A layout (or linear layout, linear arrangement) of a graph is an assignment of distinct integers from to the elements of . Equivalently, a layout may be thought of as an ordering of , where . A tree layout is a linear arrangement of a tree. If is a non-integer point on -axis, then the cut of the layout at , denoted is the number of edges that cross over , i.e. the number of edges with . The cutwidth of a layout , denoted , is the maximum cut of over all possible values; namely,
The cutwidth of a graph , denoted , is the minimum cutwidth of any linear arrangement of .
The width of a layout , , is the maximum of over all edges of . That is, it is the length of the longest edge in the layout. The bandwidth of , , is the minimum width over all layouts. A bandwidth layout for a graph is a layout satisfying .
- Bandwidth, Separation-width.