Matching planar maps

The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g., computer vision, geographic information systems, etc. More precisely, we define feasible distance measures that reflect how close a given pattern H is to some part of a larger pattern G. These distance measures are generalizations of the well-known Fréchet distance for curves. We first give an efficient algorithm for the case that H is a polygonal curve and G is a geometric graph. Then, slightly relaxing the definition of distance measure, we give an algorithm for the general case where both, H and G, are geometric graphs.     

Graph-theoretic conditions for injectivity of functions on rectangular domains

This paper presents sufficient graph-theoretic conditions for injectivity of collections of differentiable functions on rectangular subsets of Rn. The results have implications for the possibility of multiple fixed points of maps and flows. Well-known results on systems with signed Jacobians are shown to be easy corollaries of more general results presented here.     

An existence theorem for planar maps

The main result of this paper is a theorem concerning possible cubic maps on the plane or sphere. The dual approach of spherical triangulations will be used. Every such triangulation must contain a vertex of degree less than 8 and other than 5, or else contain one of a list of 5 configurations. Due to the occurrence of these five configurations in four color reduction arguments, this implies that a minimal five color map must have at least one face with six or seven neighbors. The theorem is given in Heesch [1, p. 129 ff.], but the proof here is much shorter, due to a modification of Heesch's principle of “discharging”. The principle itself is obtained by exploiting the Euler formula, and should be compared with the theory of Euler contributions as developed by Ore in [3], and by Ore and Stemple [4].     

Counting unrooted planar maps

Two planar maps are identified if one can be transformed to the other by any homeomorphism of the sphere. The number of such maps is found by determining the numbers of maps which have been rooted in various ways.     

Chromatic sum equations for rooted cubic planar maps

This paper provides a functional equation satisfied by rooted nearly cubic planar maps. By a nearly cubic map is meant such a map that all the vertices have valency 3 with the exception of at most the root-vertex. And, as a consequence, the corresponding functional equation for rooted cubic planar maps is found.     

Counting rooted unicursal planar maps

This paper investigates the number of rooted unicursal planar maps and presents some formulae for such maps with four parameters： the numbers of nonrooted vertices and inner faces and the valencies of two odd vertices.     

ENUMERATING ROOTED LOOPLESS PLANAR MAPS

This paper provides the following results.1.The equivalence between the method described by W.T.Tutte for determining parametricexpressions of certain enumerating functions and the one which the author used in [2] for findingthe parametric expression of the generating function of rooted general planar maps dependent on theedge number,is shown.2.The number of rooted boundary loop maps,i.e.,maps for each of which all the edges on theboundary of the outer face are loops,with the edge number given is found.3.The number of rooted nearly loopless planar maps,i.e.,loopless maps and maps having exactlyone loop which is just the rooted edge and does not form the boundary of the outer face,with givenedge number is also found.4.The recursive formula satisfied by the number of rooted loopless planar maps dependent onthe edge number is derived.5.In addition,the number of loop rooted maps,i.e.,maps in each of which there is only one loopwhich is just the rooted edge,dependent on the edge number is obtained at the sam     

Counting non-isomorphic three-connected planar maps

A counting formula for the number of non-isomorphic planar maps with m edges was obtained by V. A. Liskovets, and non-isomorphic 2-connected planar maps were counted by Liskovets and the author. R. W. Robinson's generalization of Polya's counting theory can be applied to these formulae to count, in polynomial time, non-isomorphic planar maps satisfying various sets of restrictions. Here two sets of planar maps are counted: maps with given 2-connected components, and 3-connected maps.     

Enumerating rooted simple planar maps

The main purpose of this paper is to find the number of combinatorially distinct rooted simpleplanar maps,i.e.,maps having no loops and no multi-edges,with the edge number given.We haveobtained the following results.1.The number of rooted boundary loopless planar [m,2]-maps.i.e.,maps in which there areno loops on the boundaries of the outer faces,and the edge number is m,the number of edges on theouter face boundaries is 2,is(?)for m≥1.G_0~N=0.2.The number of rooted loopless planar [m,2]-maps is(?)3.The number of rooted simple planar maps with m edges H_m~s satisfies the following recursiveformula:(?)where H_m~(NL) is the number of rooted loopless planar maps with m edges given in [2].4.In addition,γ(i,m),i≥1,are determined by(?)for m≥i.γ(i,j)=0,when i>j.     

Invariant curves for planar competitive and cooperative maps

In this paper we present results on the existence of invariant curves for planar maps that are monotone with respect to either the south-east or north-east ordering. Some of these curves are the stable or unstable manifolds of hyperbolic fixed points (saddle points) or non-hyperbolic fixed points, and are also the boundary of basins of attraction of such points.     

Three-colourings of planar 4-valent maps

A strong face 3-colouring of a planar 4-valent map G is a 3-colouring of the faces such that there is a face of each colour at every vertex. Such a map is one-track if it contains an Eulerian path which at each vertex regarded as a cross-roads goes directly through. It is proved that every planar 4-valent map can be strongly face 3-coloured and this can be done in a unique way if and only if G is one-track. Formulas are obtained for the number of strong face 3-colourings and the number of all face 3-colourings.     

Covalence sequences of planar vertex-homogeneous maps

Given a cyclic d-tuple of integers at least 3, we consider the class of all 1-ended 3-connected d-valent planar maps such that every vertex manifests this d-tuple as the (clockwise or counterclockwise) cyclic order of covalences of its incident faces. We obtain necessary and/or sufficient conditions for the class to contain a Cayley map, a non-Cayley map whose underlying graph is a Cayley graph, a vertex-transitive graph whose subgroup of orientation-preserving automorphisms acts (or fails to act) vertex-transitively, a non-vertex-transitive map, or no planar map at all.     

Enumeration of rooted planar halin maps

A Halin map is a kind of planar maps oriented by a tree. In this paper the rooted halin maps with the vertex partition as parameters are enumerated such that a famous result on rooted trees due to Harary. Prins, and Tutte is deduced as. a special ease. Further, by using Lagrangian inversion to obtain a number of summation free formulae dixectly, the various kinds of rooted Halin maps with up to three parameters have been counted.