Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Coupling of High Voltage AC Power Line Fields to Metallic Pipelines

In the recent years, there has been a trend to run metallic pipelines carrying petroleum products and high voltage AC power lines parallel to each other in a relatively narrow strip of land. Due to this sharing of the right-of-way, verhead AC power line electric field may induce voltages on the metallic pipelines running in close vicinity leading to serious adverse effects. In this paper, the induced voltages on metallic pipelines running in close vicinity of high voltage power transmission lines have been computed. Before computing the induced voltages, an optimum configuration of the phase conductors based on the lowest conductor surface gradient and field under transmission line has been arrived at. This paper reports the conductor surface field gradients calculated for the various configurations. Also the electric fields under transmission line, for single circuit and double circuit (various phase arrangements) have been analyzed. Based on the above results, an optimum configuration giving the lowest field under the power line as well as the lowest conductor surface gradient has been arrived at and for this configuration, induced voltage on the pipeline has been computed using the Charge Simulation Method (CSM). For comparison, induced voltages on the pipeline has been computed for the various other phase configurations also.

Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

Internal displacement reactions in multicomponent oxides: Part I. Line compounds with narrow homogeneity range

Structure and phase transition of LaO1−xF1+2x, prepared by solid-state reaction of La2O3 and LaF3, was investigated by X-ray powder diffraction and differential scanning calorimetry for both positive and negative values of the nonstoichiometric parameter x. The electrical conductivity was investigated as a function of temperature and oxygen partial pressure using AC impedance spectroscopy. Fluoride ion was identified as the migrating species in LaOF by coulometric titration and transport number determined by Tubandt technique and EMF measurements. Activation energy for conduction in LaOF was 58.5 (±0.8) kJ/mol. Conductivity increased with increasing fluorine concentration in the oxyfluoride phase, suggesting that interstitial fluoride ions are more mobile than vacancies. Although the values of ionic conductivity of cubic LaOF are lower, the oxygen partial pressure range for predominantly ionic conduction is larger than that for the commonly used stabilized-zirconia electrolytes. Thermodynamic analysis shows that the oxyfluoride is stable in atmospheres containing diatomic oxygen. However, the oxyfluoride phase can degrade with time at high temperatures in atmospheres containing water vapor, because of the higher stability of HF compared with H2O.

Suppressed rf dissipation in 107Ag17+ ion irradiated Bi2Sr2CaCu2O8 single crystals by enhanced flux line tilt modulus

We have studied the isothermal, magnetic field (H‖c) dependent rf power P(H) dissipation (Hrf‖a) in the superconducting state of Bi2Sr2CaCu2O8 single crystals prior to and after irradiation with 250 MeV 107Ag17+ ions. In the pristine state, P(H) shows an initial decrease with increase in field, reaches a minimum at HM(T) and increases monotonically for H>HM(T). This behavior arises when the electromagnetic coupling between the pancake vortices in adjacent CuO layers becomes dominant on increasing the field and minimizes the distortions of the flux lines by confining the 2D vortices. In the post irradiated state, such an initial decrease and the minimum in P(H) is not observed but only a much reduced rf dissipation that monotonically increases with field from H = 0 onwards is seen. We attribute this difference to the strong enhancement of the tilt modulus C44 of the flux lines on irradiation when the pancake vortices in adjacent CuO bilayers are pinned along the track forming a well-stacked flux line in the field direction (‖c). We have also observed that the rf dissipation disappears at a certain temperature Tsf, at which the normal core of the flux line becomes commensurate with the columnar track diameter.

New approach to distance relays with quadrilateral polar characteristic for e.h.v.-line protection

A new technique is presented using principles of multisignal relaying for the synthesis of a universal-type quadrilateral polar characteristic. The modus operandi consists in the determination of the phase sequence of a set of voltage phasors and the provision of a trip signal for one sequence while blocking for the other. Two versions, one using ferrite-core logic and another using transistor logic, are described in detail. The former version has the merit of simplicity and has the added advantage of not requiring any d.c. supply. The unit is flexible, as it permits independent control of the characteristic along the resistance and reactance axis through suitable adjustments of replica impedance angles. The maximum operating time is about 20ms for all switching angles, and with faults within 95% of the protected section. The maximum transient overreach is about 8%.

The radiation resistance of off-set series slots in microstrip line

The radiation resistance of off-set series slots has been calculated for microstrip lines using the method proposed by Breithaupt for strip lines. A suitable transformation is made to allow for the difference in structure. Curves relating the slot resistance to the microstrip length, width and off-set distance have been obtained. Microstrip slot antenna arrays are becoming important in applications where size and weight are of significance. The radiation resistance is a very significant parameter is the design of such arrays. Oliner first calculated the radiation conductance of centered series slots in strip transmission lines and that analysis was extended by Breithaupt to the off-set series slots in stripline. The radiation resistance of off-set series slots in microstrip lines is calculated in this paper and data are obtained for different slot lengths, slot widths and off-set values. An example of the use of these data in array antenna design in shown.

Acyclic edge coloring of 2-degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)<=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a'(G)<=Delta + 1. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68:1-27, 2011

Approximate synthesis formulas for microstrip line with aperture in ground plane

Approximate closed-form expressions for the propagation characteristics of a microstrip line with a symmetrical aperture in its ground plane are reported in this article. Well-known expressions for the characteristic impedance of a regular microstrip line have been modified to incorporate the effect of this aperture. The accuracy of these expressions for various values of substrate thickness, permittivity and line width has been studied in detail by fullwave simulations. This has been further verified by measurements. These expressions are easier to compute and find immense use in the design of broadband filters, tight couplers, power dividers, transformers, delay lines, and matching circuits. A broadband filter with aperture in ground plane is demonstrated in this article. (c) 2011 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2012.