Computing upward topological book embeddings of upward planar digraphs

We describe a unified approach for studying book, point-set, and simultaneous embeddability problems of upward planar digraphs. The approach is based on a linear time strategy to compute an upward planar drawing of an upward planar digraph such that all vertices are collinear. Besides having impact in relevant application domains of graph drawing and computational geometry, the presented results open new research directions in the area of upward planarity with constraints of the positions of the vertices.     

On Inequalities with Measures of Sobolev Type Embedding Theorems on Open Sets of the Real Axis

We consider some Sobolev-type spaces and obtain a necessary and sufficient condition for their embedding in a Lebesgue space.     

Second Order Nonlinear Evolution Inclusions Ⅰ： Existence and Relaxation Results

This is the first part of a work on second order nonlinear, nonmonotone evolution inclusions defined in the framework of an evolution triple of spaces and with a multivalued nonlinearity depending on both x（t） and x（t）. In this first part we prove existence and relaxation theorems. We consider the case of an usc, convex valued nonlinearity and we show that for this problem the solution set is nonempty and compact in C^1 （T, H）. Also we examine the Isc, nonconvex case and again we prove the existence of solutions. In addition we establish the existence of extremal solutions and by strengthening our hypotheses, we show that the extremal solutions are dense in C^1 （T, H） to the solutions of the original convex problem （strong relaxation）. An example of a nonlinear hyperbolic optimal control problem is also discussed.     

Some Recent Progress and Applications in Graph Minor Theory

In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough' structure of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some of these along with some other recent advances on graph minors are surveyed. Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, Grant number 16740044, by Sumitomo Foundation, by C & C Foundation and by Inoue Research Award for Young Scientists Supported in part by the Research Grant P1–0297 and by the CRC program On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia     

Nonlinear Time Series Analysis Since 1990:Some Personal Reflections

Abstract I reflect upon the development of nonlinear time series analysis since 1990 by focusing on five majorareas of development. These areas include the interface between nonlinear time series analysis and chaos,thenonparametric/semiparametric approach,nonlinear state space modelling,financial time series and nonlinearmodelling of panels of time series.     

书籍扫描图像畸变参数自动计算方法的研究

为实现书籍扫描图像的畸变自动校正,提出用多项式来描述各像素的理论灰度g(zi)与页面上对应点到扫描仪工作平面距离zi二者之间的关系。为确立该多项式,在畸变参数已知条件下扫描一幅图像,根据已知畸变参数求出zi,即可按最小二乘法原理由各像素灰度的实际值求出多项式的各个系数。实验证明,采用4阶多项式已能满足一般要求,并求出了各系数。对任意扫描图像,自动计算畸变参数的方法为:首先利用扫描图像上页边空白处各像素的灰度,对畸变参数进行估计,并求出zi的估计值;然后代入所确立的多项式,可求得g(zi);通过调整各畸变参数的估计值,直到g(zi)与gi最为接近,即得最佳畸变参数。用于图像校正实验,获得了较好的校正效果,最大误差由不校正时的41%下降到了6.9%。这使得无需用户测量并输入有关畸变参数即可进行自动校正。     

On exactness and isoperimetric profiles of discrete groups

We introduce a quasi-isometry invariant related to Property A and explore its connections to various other invariants of finitely generated groups. This allows to establish a direct relation between asymptotic dimension on one hand and isoperimetry and random walks on the other. We apply these results to reprove sharp estimates on isoperimetric profiles of some groups and to answer some questions in dimension theory.     

Structure theorem for tournaments omitting N5

A finite tournament T is tight if the class of finite tournaments omitting T is well‐quasi‐ordered. We show here that a certain tournament N₅ on five vertices is tight. This is one of the main steps in an exact classification of the tight tournaments, as explained in [10]; the third and final step is carried out in [11]. The proof involves an encoding of the indecomposable tournaments omitting N₅ by a finite alphabet, followed by an application of Kruskal's Tree Theorem. This problem arises in model theory and in computational complexity in a more general form, which remains open: the problem is to give an effective criterion for a finite set {T₁,…,T_k} of finite tournaments to be tight in the sense that the class of all finite tournaments omitting each of T₁,…,T_k is well‐quasi‐ordered. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 165–192, 2003