The problem of constructing the proper-path-decomposition of width at most 2 has an application to the efficient graph layout into ladders. In this paper, we give a linear time algorithm which, for a given graph with maximum vertex degree at most 3, determines whether the proper-pathwidth of the graph is at most 2, and if so, constructs a proper-path-decomposition of width at most 2.

We study the online file allocation problem on ring networks. In this paper, we present a 7-competitive randomized algorithm against an adaptive online adversary on uniform cactus graphs. The algorithm is deterministic if the file size is 1. Moreover, we obtain lower bounds of 4.25 and 3.833 for a deterministic algorithm and a randomized algorithm against an adaptive online adversary, respectively, on ring networks.

In this paper we consider the VLSI layout (i.e., Manhattan layout) of graphs into grids with minimum width (i.e., the length of the shorter side of a grid) as well as with minimum area. The layouts into minimum area and minimum width are equivalent to those with the largest possible aspect ratio of a minimum area layout. Thus such a layout has a merit that, by "folding" the layout, a layout of all possible aspect ratio can be obtained with increase of area within a small constant factor. We show that an N-vertex tree with layout-width k (i.e., the minimum width of a grid into which the tree can be laid out is k) can be laid out into a grid of area O(N) and width O(k). For binary tree layouts, we give a detailed trade-off between area and width: an N-vertex binary tree with layout-width k can be laid out into area and width k + α, where α is an arbitrary integer with 0 α , and the area is existentially optimal for any k 1 and α 0. This implies that α = Ω(k) is essential for a layout of a graph into optimal area. The layouts proposed here can be constructed in polynomial time. We also show that the problem of laying out a given graph G into given area and width, or equivalently, into given length and width is NP-hard even if G is restricted to a binary tree.

The path coloring problem is to assign the minimum number of colors to a given set P of directed paths on a given symmetric digraph D so that no two paths sharing an arc have the same color. The problem has applications to efficient assignment of wavelengths to communications on WDM optical networks. In this paper, we show that the path coloring problem is NP-hard even if the underlying graph of D is restricted to a binary caterpillar. Moreover, we give a polynomial time algorithm which constructs, given a binary caterpillar G and a set P of directed paths on the symmetric digraph associated with G, a path coloring of P with at most colors, where L is the maximum number of paths sharing an edge. Furthermore, we show that no local greedy path coloring algorithm on caterpillars in general uses less than colors.

It is known that the problem of determining, given a planar graph G and integers m and n, whether there exists a congestion-1 embedding of G into a two dimensional mn-grid is NP-complete. In this paper, we show that the problem is still NP-complete if G is restricted to an acyclic graph.

It is known that the problem of determining, given a planar graph G and an integer m, whether there exists a congestion-1 embedding of G into an m k-grid is NP-complete for a fixed integer k 3. It is also known that the problem for k = 3 is NP-complete even if G is restricted to an acyclic graph. The complexity of the problem for k = 2 was left open. In this paper, we show that for k = 2, the problem can be solved in polynomial time if G is restricted to a tree, while the problem is NP-complete even if G is restricted to an acyclic graph.

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.

We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2n-1-vertex complete binary tree can be embedded in a (2n/2+1)(2n/2+1)-grid and a 2n/2 2n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2n-1-vertex complete binary tree is embeddable in a 2n/2 2n/2-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2n-1-vertex complete binary tree can be embedded with unit congestion in a 2n/2 2n/2-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2n-1-vertex complete binary tree with an even integer n into a square torus with unit congestion.