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，是否在路径上添加边沿并形成循环是否会从本质上减少切割宽度。我们分别证明了二维普通和圆柱网格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}。
展开▼
