A unified approach to visibility representations of planar graphs

We studyvisibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments that intersect only adjacent vertex-segments. Every graph that admits this representation must be planar. We consider three types of visibility representations, and we give complete characterizations of the classes of graphs that admit them. Furthermore, we present linear time algorithms for testing the existence of and constructing visibility representations of planar graphs. Many applications of our results can be found in VLSI layout.This research was partially supported by the Joint Services Electronics Program under Contract N00014-84-C-0149. Roberto Tamassia was supported in part by a Fulbright grant.On leave from the Dipartmento di Informatica e Sistemistica, Universita' di Roma, La Sapienza, Via Buonarroti 12, 00185 Roma, Italy.Portions of this paper were written while this author was visting the Tektronix Computer Research Laboratory in Beaverton, Oregon, USA.     

Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme

We describe a method that serves to simultaneously determine the topological configuration of the intersection curve of two parametric surfaces and generate compatible decompositions of their parameter domains, that are amenable to the application of existing perturbation schemes ensuring exact topological consistency of the trimmed surface representations. To illustrate this method, we begin with the simpler problem of topology resolution for a planar algebraic curve F(x,y)=0 in a given domain, and then extend concepts developed in this context to address the intersection of two tensor-product parametric surfaces p(s,t) and q(u,v) defined on (s,t)∈[0,1]² and (u,v)∈[0,1]². The algorithms assume the ability to compute, to any specified precision, the real solutions of systems of polynomial equations in at most four variables within rectangular domains, and proofs for the correctness of the algorithms under this assumption are given. Mathematics subject classification (2000)  65D17     

An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

Analysis of Open Discrete Time Queueing Networks: A Refined Decomposition Approach

This paper deals with approximate analysis methods for open queueing networks. External and internal flows from and to the nodes are characterized by renewal processes with discrete time distributions of their interarrival times. Stationary distributions of the waiting time, the queue size and the interdeparture times are obtained using efficient discrete time algorithms for single server (GI/G/1) and multi-server (GI/D/c) nodes with deterministic service. The network analysis is extended to semi-Markovian representations of each flow among the nodes, which include parameters of the autocorrelation function.     

Generalized spline wavelets

A generalized multiresolution of multiplicityr, generated byr linearly independent spline functions with multiple knots, is introduced. With the help of the autocorrelation symbol and the two-scale symbol of the scaling functions, spline wavelets with multiple knots can be completely characterized. New decomposition and reconstruction algorithms, based on the Fourier technique, are presented.     

Conformal mappings from annuli to canonical doubly connected Bell representations

This paper derives formulae, expressed in terms of Schottky-Klein prime functions, for the conformal mapping between concentric annuli and Bell representations which are canonical doubly connected planar domains. New formulae relating the conformal moduli associated with the two respective canonical domains are derived and complement recent results by Jeong, Oh and Taniguchi [M. Jeong, J.-W. Oh, M. Taniguchi, Equivalence problem for annuli and Bell representations in the plane, J. Math. Anal. Appl. 325 (2007) 1295-1305].     

Zeroless arithmetic: representing integers ONLY using ONE

We use recurrence equations (alias difference equations) to enumerate the number of formula representations of positive integers using only addition and multiplication, and using addition, multiplication and exponentiation, where all the inputs are ones. We also describe efficient algorithms for the random generation of such representations, and use dynamical programming to find a shortest possible formula representing any given positive integer.     

A simple bijectio n betwee n sta ndard 3× n tableaux a nd irreducible webs for $\mathfrak{sl}_{3}$

Combinatorial spiders are a model for the invariant space of the tensor product of representations. The basic objects, webs, are certain directed planar graphs with boundary; algebraic operations on representations correspond to graph-theoretic operations on webs. Kuperberg developed spiders for rank 2 Lie algebras and \mathfrak sl₂\mathfrak {sl}_{2}. Building on a result of Kuperberg, Khovanov–Kuperberg found a recursive algorithm giving a bijection between standard Young tableaux of shape 3×n and irreducible webs for \mathfraksl₃\mathfrak{sl}_{3} whose boundary vertices are all sources.     

Small Drawings of Outerplanar Graphs,Series-Parallel Graphs,and Other Planar Graphs

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n ²) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be achieved. We show here that series-parallel graphs can be drawn in O(n ^3/2) area, and outerplanar graphs can be drawn in O(nlog n) area, but 2-outerplanar graphs and planar graphs of proper pathwidth 3 require Ω(n ²) area. Our drawings are visibility representations, which can be converted to polyline drawings of asymptotically the same area.     

Improved planarity algorithms

Three planarity algorithms PA-1, PA-2, and PA-3 are presented which are substantial improvements upon those of Demoucronet al. and Rubin, respectively. The algorithms test the planarity of a graphG by attempting to embed it into the plane step by step. If such an embedding can succeed,G is determined as planar and its planar representation is acquired simultaneously. Among others, PA-3 has been implemented in ALGOL on UNIVAC-1100. The program takes about 13.5 seconds to test a graph of 1000 vertices and 2994 edges.     

Smoothness characterization and stability of nonlinear and non-separable multiscale representations

The aim of the paper is the construction and the analysis of nonlinear and non-separable multiscale representations for multivariate functions defined using a non-diagonal dilation matrix M. We show that a function in L^p or Besov spaces can be characterized by means of its multiscale representation. We also study the stability of these representations, a key issue to design adaptive algorithms.     

Computing Complex Airy Functions by Numerical Quadrature

Integral representations are considered of solutions of the Airy differential equation w –zw=0 for computing Airy functions for complex values of z. In a first method contour integral representations of the Airy functions are written as non-oscillating integrals for obtaining stable representations, which are evaluated by the trapezoidal rule. In a second method an integral representation is evaluated by using generalized Gauss–Laguerre quadrature; this approach provides a fast method for computing Airy functions to a predetermined accuracy. Comparisons are made with well-known algorithms of Amos, designed for computing Bessel functions of complex argument. Several discrepancies with Amos' code are detected, and it is pointed out for which regions of the complex plane Amos' code is less accurate than the quadrature algorithms. Hints are given in order to build reliable software for complex Airy functions.     

Integral representations for computing real parabolic cylinder functions

Summary. Integral representations are derived for the parabolic cylinder functions U(a,x), V(a,x) and W(a,x) and their derivatives. The new integrals will be used in numerical algorithms based on quadrature. They follow from contour integrals in the complex plane, by using methods from asymptotic analysis (saddle point and steepest descent methods), and are stable starting points for evaluating the functions U(a,x), V(a,x) and W(a,x) and their derivatives by quadrature rules. In particular, the new representations can be used for large parameter cases. Relations of the integral representations with uniform asymptotic expansions are also given. The algorithms will be given in a future paper.Mathematics Subject Classification (2000): 33C15, 41A60, 65D20Revised version received July 25, 2003     

Bifurcations of travelling wave solutions for the mK(n, n) equation

Using the method of planar dynamical systems to the mK(n, n) equation, the existence of uncountably infinite many smooth and non-smooth periodic wave solutions, solitary wave solutions and kink and anti-kink wave solutions is proved. Under different parametric conditions, various sufficient conditions to guarantee the existence of the above solutions are given. All possible exact explicit parametric representations of smooth and non-smooth travelling wave solutions are obtain.     

Some exact representations for the mass current in3He-A and their zero temperature implications

New representations for the mass current in the A-phase of helium-3 are obtained from an exact solution of the Dyson-Gor'kov equation. Expansions of these representations in powers of a small parameter which characterizes the London limit is considered. A previously known formula for the current is obtained to the main order for zero temperature. The corresponding higher terms are estimated. Bibliography:19 titles. Dedicated to the memory of my teacher, Victor Nicolaevich Popov Published inZapiski Nauchnykh Seminarov POMI, Vol. 224, 1995, pp. 250–266. Translated by K. Malyshev.     

A Rational-Function Identity Related to the Murnaghan–Nakayama Formula for the Characters of S n

The Murnaghan–Nakayama formula for the characters of S _n is derived from Young's seminormal representation, by a direct combinatorial argument. The main idea is a rational function identity which when stated in a more general form involves Möbius functions of posets whose Hasse diagrams have a planar embedding. These ideas are also used to give an elementary exposition of the main properties of Young's seminormal representations.     

On correlation functions of the XY model

New determinant representations are obtained for the simplest correlation functions of the Heisenberg XY spin chain. Bibliography: 8 titles. Dedicated to the memory of V. N. Popov Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 224, 1995, pp. 178–191.     

New algorithms for selection

New algorithms are presented to select the k largest elements, and give their respective order, of a totally ordered set of n elements, when k is small compared to n. The performance of these algorithms improves over that of previously known algorithms. One of these algorithms is optimal for a wide range of values of n and k. The algorithms can be modified to select the k th largest element only. The performance of the modified algorithms improves, for asymptotic values of n, over that of previously known algorithms for selecting the k th largest element.     

Resolvent estimates and scattering matrix for N-particle Hamiltonians

New estimates for the resolvent of theN-particle Schrödinger operator are established. The estimates obtained allow us to give stationary representations for the corresponding scattering matrix. In particular, it is shown that the scattering matrix is a strongly continuous function of the spectral parameter (energy).     

Decompositions of root systems of Kac-Moody algebras of rank 2

A classifications is presented of the parabolic decompositions of the system of roots of Kac- Moody algebras of rank 2. New series of irreducible representations are constructed.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 12, pp. 1712–1715, December, 1992.