A Linear Time Algorithm for Constructing Maximally Symmetric Straight Line Drawings of Triconnected Planar Graphs

Symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. To draw graphs symmetrically, we employ two steps. The first step is to find appropriate automorphisms. The second step is to draw the graph to display the automorphisms. Our aim in this paper is to construct maximally symmetric straight line drawings of triconnected planar graphs in linear time. Previously known algorithms run in quadratic time. We show that an algorithm of Fontet can be used to find an embedding in the plane with the maximum number of symmetries, and present a new algorithm for finding a straight line drawing that achieves that maximum. Both algorithms run in linear time.     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

Long-Term Changes in a Heat Exchanger Steel

The steel ASTM A213 P22 is used for superheater outlet header in power plants. During duty cycles lasting over tens of years the temperature is of the order of 545°C and the pressure 125 atm. The microscopic changes in these steels are hard to analyze under working conditions, but they are believed to be responsible for the appearance of creeps in such devices. Investigation of the microscopic modifications will help to predict future failures due to creeps, increasing the reliability and saving a lot of money.We report the investigation of such changes in ASTM A213 P22 steel in use for 30 years as a Superheater header at Haifa power station. The analysis has been carried out using Mössbauer Spectroscopy, X-ray diffraction and optical microscopy. As a result it seems that the morphology and phase change of the carbide phases M₃C/M₇C₃ and M₂₃C₆ are the most prominent changes leading to the material failures.     

On the evolution of islands

Letn cells be arranged in a ring, or alternatively, in a row. Initially, all cells are unmarked. Sequentially, one of the unmarked cells is chosen at random and marked until, aftern steps, each cell is marked. After thekth cell has been marked the configuration of marked cells defines some number of islands: maximal sets of adjacent marked cells. Let ξ _k denote the random number of islands afterk cells have been marked. We give explicit expressions for moments of products of ξ _k ’s and for moments of products of 1/ξ _k ’s. These are used in a companion paper to prove that if a random graph on the natural number is made by drawing an edge betweeni≧1 andj>i with probabilityλ/j, then the graph is almost surely connected ifλ>1/4 and almost surely disconnected ifλ≦1/4.