On the complexity of the planar directed edge-disjoint paths problem

The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs and demand graphs consisting of two sets of parallel edges.     

Caterpillar arboricity of planar graphs

We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets (E_i)_1?i?4 in such a way that G[E_i], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G.     

The surface shear viscosity of a planar liquid-vapor interface I. Theory

In this paper we develop a theory for the calculation of the surface shear viscosity of a planar liquid-vapor interface. The theory is an extension of the generalized hydrodynamics formalism, originally developed for the calculation of linear transport coefficients in isotropic bulk fluids. We develop an expression for the surface shear viscosity in terms of the actual shear viscosity profile in the interfacial region. We derive an expression for this profile in terms of the first four moments of the autocorrelation function of the transverse parallel velocity (the component of velocity parallel to k, which is the projection of k on to the interface). Finally, we calculate these moments for a planar liquid-vapor interface.     

On the Characterization of the Dynamic Performances of Planar Manipulators

The characterization of the dynamic performances of a manipulator is important both to compare different manipulators and to improve the dynamic performances of a manipulator during the design stage. In a previous paper the concepts of swiftness and of dynamic isotropy were used to characterize some dynamic performances of 3-dof manipulators. This paper analyzes the usefulness of these concepts for three-dof planar manipulators and shows that the concept of swiftness is still significant, whereas the concept of dynamic isotropy has no practical interest. Moreover, it introduces three new dynamic properties that are useful in the design of a 3-dof planar manipulator. Finally, it proposes some indices that measure both the swiftness and the three new dynamic properties and shows how to use them, both for evaluating the dynamic performances of a given 3-dof planar manipulator and for improving the dynamic performances during its design.     

Finding efficient solutions for rectilinear distance location problems efficiently

Given n planar existing facility locations, a planar new facility location X is called efficient if there is no other location Y for which the rectilinear distance between Y and each existing facility is at least as small as between X and each existing facility, and strictly less for at least one existing facility. Rectilinear distances are typically used to measure travel distances between points via rectilinear aisles or street networks. We first present a simple arrow algorithm, based entirely on geometrical analysis, that constructs all efficient locations. We then present a row algorithm which is of order n(log n) that constructs all efficient locations, and establish that no alternative algorithm can be of a lower order.     

Fundamental sloshing frequencies of stratified two-fluid systems in closed prismatic tanks

The solution to the irrotational eigenvalue problem for internal waves in closed tanks is simple but not easily accessible. Solutions are given for two geometries frequently encountered in industry. It is recommended that acoustic rather than structural elements be used in finite-element calculations of complex geometries     

Hard coloring problems in low degree planar bipartite graphs

In this paper we prove that the PRECOLORING EXTENSION problem on graphs of maximum degree 3 is polynomially solvable, but even its restricted version with 3 colors is NP-complete on planar bipartite graphs of maximum degree 4.The restricted version of LIST COLORING, in which the union of all lists consists of 3 colors, is shown to be NP-complete on planar 3-regular bipartite graphs.     

Rainbow number of matchings in planar graphs

The rainbow number$rb(G,H)$ for the graph $H$ in $G$ is defined to be the minimum integer $c$ such that any $c$-edge-coloring of $G$ contains a rainbow $H$. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching $k{K}_2$ in the plane triangulations, where the gap between the lower and upper bounds is $O\left(k^3\right)$. In this paper, we show that the rainbow number of the matching $k{K}_2$ in maximal outerplanar graphs of order $n$ is $n+O\left(k\right)$. Using this technique, we show that the rainbow number of the matching $k{K}_2$ in some subfamilies of plane triangulations of order $n$ is $2n+O\left(k\right)$. The gaps between our lower and upper bounds are only $O\left(k\right)$.     

Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable

It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable (Borodin et al., 2005) [13] and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable (Borodin et al., 2006) [11]. We give a common extension of these results by proving that every planar graph in which no triangles have common edges with k-cycles, where k∈{4,5,7} (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable.     

Morse index and stability of elliptic Lagrangian solutions in the planar three-body problem

We illustrate a new way to study the stability problem in celestial mechanics. In this paper, using the variational nature of elliptic Lagrangian solutions in the planar three-body problem, we study the relation between Morse index and its stability via Maslov-type index theory of periodic solutions of Hamiltonian system. For elliptic Lagrangian solutions we get an estimate of the algebraic multiplicity of unit eigenvalues of its monodromy matrix in terms of the Morse index, which is the key to understand the stability problem. As a special case, we provide a criterion to spectral stability of relative equilibrium.