The cutwidth problem is to find a linear layout of a network so that the maximal number of cuts (cw) of a line separating consecutive vertices is minimized. A related and more natural problem is the cyclic cutwidth (ccw) when a circular layout is considered. The main question is to compare both measures cw and ccw for specific networks, whether adding an edge to a path and forming a cycle reduces the cutwidth essentially. We prove exact values for the cyclic cutwidths of the 2-dimensional ordinary and cylindrical meshes P_m x P_n and P_m x C_n, respecitvely. Especially, if m >= n + 3, then ccw(P_m x P_n) = cw(P_m x P_n) = n + 1 and if n is even then ccw(P_n x P_n) = n - 1 and cw(P_n x P_n) = n + 1 and if m >= 2, n >= 3, then ccw(P_m x C_n) = min{m + 1, n + 2}.
展开▼
机译：截污问题是找到网络的线性布局，使得分离连续顶点的线的最大数量的切割（CW）最小化。当考虑圆形布局时，相关和更自然的问题是循环截云（CCW）。主要问题是比较特定网络的措施CW和CCW，无论是向路径添加边缘并形成循环的基本还会减少截云。 Repecitipely，我们证明了二维普通和圆柱网的循环截云P_M X P_N和P_M X C_N的精确值。特别是，如果m> = n + 3，则ccw（p_m x p_n）= cw（p_m x p_n）= n + 1，如果n是ccw（p_n x p_n）= n - 1和cw（p_n x p_n） ）= n + 1，如果m> = 2，n> = 3，则ccw（p_m x c_n）= min {m + 1，n + 2}。
展开▼
