An Euler‐genus approach to the calculation of the crosscap‐number polynomial

In 1994, J. Chen, J. Gross, and R. Rieper demonstrated how to use the rank of Mohar's overlap matrix to calculate the crosscap‐number distribution, that is, the distribution of the embeddings of a graph in the nonorientable surfaces. That has ever since been by far the most frequent way that these distributions have been calculated. This article introduces a way to calculate the Euler‐genus polynomial of a graph, which combines the orientable and the nonorientable embeddings, without using the overlap matrix. The crosscap‐number polynomial for the nonorientable embeddings is then easily calculated from the Euler‐genus polynomial and the genus polynomial.     

The genus distributions for a certain type of permutation graphs in orientable surfaces

A circuit is a connected nontrivial 2-regular graph.A graph G is a permutation graph over a circuit C,if G can be obtained from two copies of C by joining these two copies with a perfect matching.In this paper,based on the joint tree method introduced by Liu,the genus polynomials for a certain type of permutation graphs in orientable surfaces are given.     

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied.There are three approaches to solve this problem.The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths;the second approach is to find a current assignment of the current graph by the theory of current graph;the third approach is to find exponentially many embedding(or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph.According to this three approaches,we can construct exponentially many minimum genus embeddings of complete graph K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

两类四正则图的完全亏格分布

一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文利用刘彦佩提出的嵌入的联树模型,得出了两类新的四正则图的完全亏格多项式,并推导出已有结果的两类图的完全亏格多项式.此处的结果形式更为简单.     

关于循环图的曲面嵌入

该文集中探讨循环图的曲面嵌入性质.决定了所有循环图的最小亏格(其中包括可定向亏格与不可定向亏格)和最大亏格.对于固定的整数l(≥3)和充分大的 自然数n,只有一种方式将4 -正则循环图C(n,l)嵌入到环面上使得其每一个面都是4 -边形.特别地,循环图$C(2l+2,l)$在加入若干条新边后可以同时将环面与Klein瓶进行三角剖分.     

Total embedding distributions of Ringel ladders

The total embedding distributions of a graph consists of the orientable embeddings and non-orientable embeddings and are known for only a few classes of graphs. The orientable genus distribution of Ringel ladders is determined in [E.H. Tesar, Genus distribution of Ringel ladders, Discrete Mathematics 216 (2000) 235–252] by E.H. Tesar. In this paper, using the overlap matrix, we obtain nonhomogeneous recurrence relation for rank distribution polynomial, which can be solved by the Chebyshev polynomials of the second kind. The explicit formula for the number of non-orientable embeddings of Ringel ladders is obtained. Also, the orientable genus distribution of Ringel ladders is re-derived.     

Genus spectra for symmetric embeddings of graphs on surfaces

This paper gives an account of some very recent work by the author in determining all regular maps on surfaces of Euler characteristic −1 to −200 (orientable and non-orientable), observing patterns in the resulting data, and joint work with Jozef Siráň and Tom Tucker in proving the existence of infinitely many gaps in the genus spectrum of regular but chiral maps (on orientable surfaces) and the genus spectrum of reflexible regular maps on orientable surfaces with simple underlying graph.     

循环图C(n,m)}的最小亏格

本文给出了所有循环图的可定向与不可定向最小亏格. 同时, 也给出了部分循环图的强最小亏格.     

Incompressible surfaces in handlebodies and boundary reducible 3-manifolds

We study the existence of incompressible embeddings of surfaces into the genus two handlebody. We show that for every compact surface with boundary, orientable or not, there is an incompressible embedding of the surface into the genus two handlebody. In the orientable case the embedding can be either separating or non-separating. We also consider the case in which the genus two handlebody is replaced by an orientable 3-manifold with a compressible boundary component of genus greater than or equal to two.     

Enumeration of multi-colored rooted maps

We present a study of n-colored rooted maps in orientable and locally orientable surfaces. As far as we know, no work on these maps has yet been published. We give a system of n functional equations satisfied by n-colored orientable rooted maps regardless of genus and with respect to edges and vertices. We exhibit the solution of this system as a vector where each component has a continued fraction form and we deduce a new equation generalizing the Dyck equation for rooted planar trees. Similar results are shown for n-colored rooted maps in locally orientable surfaces.     

On the genus of the semidirect product of ℤ9 by ℤ3

We show that the non-commutative semidirect product Γ of ?₉ by ?₃ has orientable genus 4. In other words, some Cayley graph of Γ embeds in an orientable surface of genus 4 (Euler characteristic ?6), but no Cayley graph of Γ embeds in an orientable surface of genus less than 4 (Euler characteristic greater than ?6). We also show that some Cayley graph of Γ embeds in a (non-orientable) surface of Euler characteristic ?3, but no Cayley graph of Γ embeds in a surface of Euler characteristic greater than ?3. Γ is the first known example of a group whose orientable Euler characteristic and non-orientable Euler characteristic differ by more than 1. Our results also complete the determination of the orientable genus of each group of order less than 32.     

Schnyder Woods for Higher Genus Triangulated Surfaces,with Applications to Encoding

Schnyder woods are a well-known combinatorial structure for plane triangulations, which yields a decomposition into three spanning trees. We extend here definitions and algorithms for Schnyder woods to closed orientable surfaces of arbitrary genus. In particular, we describe a method to traverse a triangulation of genus g and compute a so-called g-Schnyder wood on the way. As an application, we give a procedure to encode a triangulation of genus g and n vertices in 4n+O(glog (n)) bits. This matches the worst-case encoding rate of Edgebreaker in positive genus. All the algorithms presented here have execution time O((n+g)g) and hence are linear when the genus is fixed. Extended version of the article appeared in the Proc. of the ACM SoCG 2008. Part of the first author’s work was done during his visit to the CS Department of Université Libre de Bruxelles (Belgium).     

多重闭梯图在曲面上嵌入的分类

利用刘彦佩提出的嵌入的联树模型,得到了二重闭梯图在可定向曲面上的亏格分布的一个递推关系,并进一步给出了多重闭梯图在射影平面上的嵌入个数.     

The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

Exotic Minimal Surfaces

We prove a general fusion theorem for complete orientable minimal surfaces in ?³ with finite total curvature. As a consequence, complete orientable minimal surfaces of weak finite total curvature with exotic geometry are produced. More specifically, universal surfaces (i.e., surfaces from which all minimal surfaces can be recovered) and space-filling surfaces with arbitrary genus and no symmetries.     

Power graphs of (non)orientable genus two

The power graph of a finite group is the graph whose vertex set is the group, two distinct elements being adjacent if one is a power of the other. In this article, we classify the finite groups whose power graphs have (non)orientable genus two.     

关于嵌入图的最大亏格

不依赖图的其它参数, 而主要依据图嵌入在定向曲面上的有关嵌入性质, 该文研究图的最大亏格.     

Regular embeddings of coloured digraphs

A particular kind of 2-cell embeddings, called regular, for arc-coloured digraphs is introduced, and a method for constructing both orientable and non-orientable regular embeddings is presented. Furthermore, by using combinatorial concepts and the Euler-Poincaré formula, we derive upper bounds for both the orientable and non-orientable genera of such arc-coloured digraphs.Work performed within the project Geometria delle Varietà Differenziabili of the MPI of Italy.     

串联双路图的亏格分布

计算双路图的亏格分布是拓扑图论关注的一个问题,利用传递矩阵与向量积矩阵,给出了两类由双路图串联构建而成的两类闭链图的亏格分布.     

Knot exteriors with all possible meridional essential surfaces

We show the existence of infinitely many knots where each exterior contains meridional essential surfaces of independently unbounded genus and number of boundary components. In particular, we construct examples of knot exteriors each of which has all possible compact orientable surfaces embedded as meridional essential surfaces. From these results, we also prove the existence of a hyperbolic knot exterior, not necessarily of a knot in the 3-sphere, for which there are meridional essential surfaces of simultaneously unbounded genus and number of boundary components.