For a given 2-edge-connected graph G and a spanning tree T of G, the graph augmentation problem 2ECA (T,G) is to find a minimum edge set AE (G) such that T A is 2-edge-connected. This note proves that 2ECA (T, G) is solvable in polynomial time if G is series-parallel.

Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.

This paper presents a practical fault-tolerant architecture for mesh parallel machines that has t spare processors and has 2(t+2) communication links per processor while tolerating at most t+1 processor and link faults. We also show that the architecture presented here can be laid out efficiently in a linear area with wire length at most O(t).

This note considers a problem of minimum length scheduling for a set of messages subject to precedence constraints for switching and communication networks, and shows some improvements upon previous results on the problem.

A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n3) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.

The finite reconfigurability and local reconfigurability of graphs were proposed by Sha and Steiglitz [1], [2] in connection with a problem of on-line reconfiguraion of WSI networks for run-time faults. It is shown in [2] that a t-locally-reconfigurable graph for a 2-dimensional N-vertex array AN can be constructed from AN by adding O(N) vertices and edges. We show that Ω(N) vertices must be added to an N-vertex graph GN in order to construct a t-locally-reconfigurable graph for GN, which means that the number of added vertices for the above mentioned t-locally-reconfigurable graph for AN is optimal to within a constant factor. We also show that a t-finitely-reconfigurable graph for an N-vertex graph GN can be constructed from GN by adding t vertices and tN + t (t+1)/2 edges.

This note shows an efficient implementation of de Bruijn networks by the Optical Transpose Interconnection System (OTIS) extending previous results by Coudert, Ferreira, and Perennes [2].

In this paper we show that an outerplanar graph G with maximum degree at most 3 has a 2-D orthogonal drawing with no bends if and only if G contains no triangles. We also show that an outerplanar graph G with maximum degree at most 6 has a 3-D orthogonal drawing with no bends if and only if G contains no triangles.