On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.

Extending lagrange interpolation to develop a 4-node quadrilateral element

Today finite element method is a well established tool in engineering analysis and design. Though there axe many two and three dimensional finite elements available, it is rare that a single element performs satisfactorily in majority of practical problems. The present work deals with the development of 4-node quadrilateral element using extended Lagrange interpolation functions. The classical univariate Lagrange interpolation is well developed for 1-D and is used for obtaining shape functions. We propose a new approach to extend the Lagrange interpolation to several variables. When variables axe more than one the method also gives the set of feasible bubble functions. We use the two to generate shape function for the 4-node arbitrary quadrilateral. It will require the incorporation of the condition of rigid body motion, constant strain and Navier equation by imposing necessary constraints. The procedure obviates the need for isoparametric transformation since interpolation functions are generated for arbitrary quadrilateral shapes. While generating the element stiffness matrix, integration can be carried out to the accuracy desired by dividing the quadrilateral into triangles. To validate the performance of the element which we call EXLQUAD4, we conduct several pathological tests available in the literature. EXLQUAD4 predicts both stresses and displacements accurately at every point in the element in all the constant stress fields. In tests involving higher order stress fields the element is assured to converge in the limit of discretisation. A method thus becomes available to generate shape functions directly for arbitrary quadrilateral. The method is applicable also for hexahedra. The approach should find use for development of finite elements for use with other field equations also.

Finite element simulation of BAW propagation in inhomogeneous plate due to piezoelectric actuation

A set of finite elements (FEs) is formulated to analyze wave propagation through inhomogeneous material when subjected to mechanical, thermal loading or piezo-electric actuation. Elastic, thermal and electrical properties of the materials axe allowed to vary in length and thickness direction. The elements can act both as sensors and actuators. These elements are used to model wave propagation in functionally graded materials (FGM) and the effect of inhomogeneity in the wave is demonstrated. Further, a surface acoustic wave (SAW) device is modeled and wave propagation due to piezo-electric actuation from interdigital transducers (IDTs) is studied.

On breaks of the Indian monsoon

For over a century, the term break has been used for spells in which the rainfall over the Indian monsoon zone is interrupted. The phenomenon of 'break monsoon' is of great interest because long intense breaks are often associated with poor monsoon seasons. Such breaks have distinct circulation characteristics (heat trough type circulation) and have a large impact on rainfed agriculture. Although interruption of the monsoon rainfall is considered to be the most important feature of the break monsoon, traditionally breaks have been identified on the basis of the surface pressure and wind patterns over the Indian region. We have defined breaks (and active spells) on the basis of rainfall over the monsoon zone. The rainfall criteria are chosen so as to ensure a large overlap with the traditional breaks documented by Ramamurthy (1969) and De et al (1998). We have identified these rainbreaks for 1901-89. We have also identified active spells on the basis of rainfall over the Indian monsoon zone. We have shown that the all-India summer monsoon rainfall is significantly negatively correlated with the number of rainbreak days (correlation coefficient -0.56) and significantly positively correlated with the number of active days (correlation coefficient 0.47). Thus the interannual variation of the all-India summer monsoon rainfall is shown to be related to the number of days of rainbreaks and active spells identified here. There have been several studies of breaks (and also active spells in several cases) identified on the basis of different criteria over regions differing in spatial scales (e.g., Webster et al 1998; Krishnan et al 2000; Goswami and Mohan 2000; and Annamalai and Slingo 2001). We find that there is considerable overlap between the rainbreaks we have identified and breaks based on the traditional definition. There is some overlap with the breaks identified by Krishnan et al (2000) but little overlap with breaks identified by Webster et al (1998). Further, there are three or four active-break cycles in a season according to Webster et al (1998) which implies a time scale of about 40 days for which Goswami and Mohan (2000), and Annamalai and Slingo'(2001) have studied breaks and active minus break fluctuations. On the other hand, neither the traditional breaks (Ramamurthy 1969; and De et al 1998) nor the rainbreaks occur every year. This suggests that the 'breaks' in these studies axe weak spells of the intraseasonal variation of the monsoon, which occur every year. We have derived the OLR and circulation patterns associated with rainbreaks and active spells and compared them with the patterns associated with breaks/active minus break spells from these studies. Inspite of differences in the patterns over the Indian region, there is one feature which is seen in the OLR anomaly patterns of breaks identified on the basis of different criteria as well as the rainbreaks identified in this paper viz., a quadrapole over the Asia-west Pacific region arising from anomalies opposite (same) in sign to those over the Indian region occurring over the equatorial Indian Ocean and northern tropical (equatorial) parts of the west Pacific. Thus it appears that this quadrapole is a basic feature of weak spells of the intraseasonal,variation over the Asia-west Pacific region. Since the rainbreaks are intense weak spells, this basic feature is also seen in the composite patterns of these breaks. We find that rainbreaks (active spells) are also associated with negative (positive) anomalies over a part of the cast Pacific suggesting that the convection over the Indian region is linked to that over the east Pacific not only on the interannual scale (as evinced by the link between the Indian summer monsoon rainfall and ENSO) but on the intraseasonal scale as well.

Turbulent flow computations using upwind RANS technique for a flat plate and an airfoil

Reynolds Averaged Navier Stokes (RANS) equations are solved using third order upwind biased Roe's scheme for the inviscid fluxes and second order central difference scheme for the viscous fluxes. The Baldwin & Lomax turbulence model is employed for Reynolds stresses. The governing equations are solved using finite-volume implicit scheme in body fitted curvilinear coordinate O-grid system. Computations axe reported for a flat plate apart from RAE 2822 and NACA 0012 airfoils. Results for the flat plate at M = 0.3, R-c = 4.0 x 10(6) compare favourably with the analytical solution. Results for the two airfoils are compared with experiment. There is a good agreement in C-p distribution between experiment and computation for both the airfoils. Comparison of C-f distribution with experiment for RAE 2822 airfoil is reasonable.