The genus of the GRAY graph is 7

Using the genus embedding of the Cartesian product of three triangles we prove one can embed the smallest cubic semisymmetric graph on 54 vertices, the so-called Gray graph, in the orientable surface of genus 7, and we prove that such an embedding is optimal.     

A relative maximum genus graph embedding and its local maximum genus

A relative embedding of a connected graph is an embedding of the graph in some surface with respect to some closed walks, each of which bounds a face of the embedding. The relative maximum genus of a connected graph is the maximum of integerk with the property that the graph has a relative embedding in the orientable surface withk handles. A polynomial algorithm is provided for constructing relative maximum genus embedding of a graph if the relative tree of the graph is planar. Under this condition, just like maximum genus embedding, a graph does not have any locally strict maximum genus.     

一个关于近-三角剖分嵌入的内插定理

一个近三角剖分嵌入是指一个图嵌入在一个曲面上,使得至多可能有一个面不是三角面。在本文中我们证明了如下结果：如果一个图G在某个可定向曲面S_h上有三角剖分嵌入,那么G在S_k上有一个近三角剖分嵌入,这里k=h,h 1,…,[β(G)/2],而β(G)是图G的Betti数。     

极大平面图在不可定向曲面上强嵌入的一个注记

§ 1　IntroductionA strong embeddingμ( G) of a graph G in a surface S is such an embedding thateachface boundary of the surface is a circuit.( A strong embedding is also sometimes called acircular embedding,see[1 ] orclosed2 -cell embedding[2 ] ) .Graphsconsidered here are sim-ple( that is,they have no loops or multiple edges) .Terminology here follows those in[3] .In[1 ] ,Richter,Seymour and Siran proved that every3-connected planar graph canbe strongly embedded on some non-orientable sur…     

局部大边宽嵌入图的面圈和C-桥的结构

In this paper,we show that for a locally LEW-embedded 3-connected graph G in orientable surface,the following results hold:1) Each of such embeddings is minimum genus embedding;2) The facial cycles are precisely the induced nonseparating cycles which implies the uniqueness of such embeddings;3) Every overlap graph O(G,C) is a bipartite graph and G has only one C-bridge H such that CUH is nonplanar provided C is a contractible cycle shorter than every noncontractible cycle containing an edge of C.This ext...     

The Relative Maximum Genus of a Graph

A relative embedding of a graph in a surface with respect to a set of closed walks is one where each of the prescribed closed walks bounds a face of the embedding In the special case where the set of closed walks is empty, this amounts to the usual concept of a graph embedding. We present a formula for the maximum (orientable) genus of the surface on which a graph has a relative embedding with respect to a set of closed walks.     

Complete regular dessins of odd prime power order

A dessin is a 2-cell embedding of a connected 2-coloured bipartite graph into an orientable closed surface. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts regularly on the edges. In this paper we employ group-theoretic method to determine and enumerate the isomorphism classes of regular dessins with complete bipartite underlying graphs of odd prime power order.     

Bi-Embeddings of Steiner Triple Systems of Order 15

 It was shown by Gerhard Ringel that one of the three non-isomorphic Steiner triple systems of order 15 having an automorphism of order 5 may be bi-embedded as the faces of a face 2-colourable triangular embedding of K ₁₅ in a suitable orientable surface. Ringel's bi-embedding was obtained from an appropriate current graph. In a recent paper, the present authors showed that a second STS(15) of this type may also be bi-embedded. In the present paper we show that this second bi-embedding may also be obtained from a current graph. Furthermore, we exhibit a third current graph which yields a bi-embedding of the third STS(15) of this type. Received: October 5, 1998     

Two maps on one surface

Two embeddings of a graph in a surface S are said to be “equivalent” if they are identical under an homeomorphism of S that is orientation‐preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be “jointly embedded” if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge‐crossings; this minimum we call the “joint crossing number” of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction for re‐embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its “mirror image,” then the joint crossing number can decrease, but not by more than 6.066%. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 198–216, 2001     

Nonrealizable Minimal Vertex Triangulations of Surfaces: Showing Nonrealizability Using Oriented Matroids and Satisfiability Solvers

We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in ℝ³. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. Correcting a previous error in the literature, we construct the first infinite family of such nonrealizable triangulations of surfaces. These results were achieved by transforming the problem of finding suitable oriented matroids into a satisfiability problem. This method can be applied to other geometric realizability problems, e.g., for face lattices of polytopes.     

Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.     

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.     

类圈图的亏格分布

一个图 G 的亏格分布是指序列{g_k}, g_k表示 G 嵌入亏格为 k 的闭的可定向曲面的数目. 该文给出了标准类圈图的亏格分布的递推公式, 并得到类圈图的嵌入多项式的计算公式.     

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.     

Maximum Genus of Strong Embeddings

The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover.Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.     

Even polyhedral decompositions of cubic graphs

An even polyhedral decomposition of a finite cubic graph G is defined as a set of elementary cycles of even length in G with the property that each edge of G lies in exactly two of them. If G has chromatic index three, then G has an even polyhedral decomposition. We show that, contrary to a theorem of Szekkeres [2], this property to have an even polyhedral decomposition doesn't characterize the cubic graphs of chromatic index three. In particular, there exists an infinite family of sharks all having an even polyhedral decomposition.     

Self-dual embeddings of complete multipartite graphs

In this paper we examine self-dual embeddings of complete multipartite graphs, focusing primarily on K_m(n) having m parts each of size n. If m = 2, then n must be even. If the embedding is on an orientable surface, then an Euler characteristic argument shows that no such embedding exists when n is odd and m ? 2, 3 (mod 4); there is no such restriction for embeddings on nonorientable surfaces. We show that these embeddings exist with a few small exceptions. As a corollary, every group has a Cayley graph with a self-dual embedding. Our main technique is an addition construction that combines self-dual embeddings of two subgraphs into a self-dual embedding of their union. We also apply this technique to nonregular multipartite graphs and to cubes.     

Polyhedral embeddings in the projective plane

We characterize the graphs that have polyhedral embeddings in the projective plane. We also prove that if one embedding of a graph is polyhedral then all embeddings of that graph are polyhedral.     

关于嵌入图的最大亏格

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