# Layout

Перейти к:навигация, поиск

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

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

$cut({\mathcal L}) = \max_{1 < p < |V|} cut_{{\mathcal L}}(p).$

The cutwidth of a graph $G$, denoted $cut(G)$, is the minimum cutwidth of any linear arrangement of $G$.

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