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.     

Enumerating reflexible 2-cell embeddings of connected graphs

Two 2-cell embeddings:X → S and j:X → S of a connected graph X into a closed orientable surface S are congruent if there are an orientation-preserving surface homeomorphism h on S and a graph automorphism γ of X such that h = γj.A 2-cell embedding:X → S of a graph X into a closed orientable surface S is described combinatorially by a pair(X;ρ) called a map,where ρ is a product of disjoint cycle permutations each of which is the permutation of the darts of X initiated at the same vertex following the orientation of S.The mirror image of a map(X;ρ) is the map(X;ρ 1),and one of the corresponding embeddings is called the mirror image of the other.A 2-cell embedding of X is reflexible if it is congruent to its mirror image.Mull et al.[Proc Amer Math Soc,1988,103:321-330] developed an approach for enumerating the congruence classes of 2-cell embeddings of graphs into closed orientable surfaces.In this paper we introduce a method for enumerating the congruence classes of reflexible 2-cell embeddings of graphs into closed orientable surfaces,and apply it to the complete graphs,the bouquets of circles,the dipoles and the wheel graphs to count their congruence classes of reflexible or nonreflexible(called chiral) embeddings.     

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.     

STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES

In this paper, the authors discuss the upper bound for the genus of strong embeddings for 3-connected planar graphs on higher surfaces. It is shown that the problem of determining the upper bound for the strong embedding of 3-connected planar near-triangulations on higher non-orientable surfaces is NP-hard. As a corollary, a theorem of Richter, Seymour and Siran about the strong embedding of 3-connected planar graphs is generalized to orientable surface.     

Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.     

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

§ 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…     

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.     

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.     

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

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

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.     

Oriented matroids and complete-graph embeddings on surfaces

We provide a link between topological graph theory and pseudoline arrangements from the theory of oriented matroids. We investigate and generalize a function f that assigns to each simple pseudoline arrangement with an even number of elements a pair of complete-graph embeddings on a surface. Each element of the pair keeps the information of the oriented matroid we started with. We call a simple pseudoline arrangement triangular, when the cells in the cell decomposition of the projective plane are 2-colorable and when one color class of cells consists of triangles only. Precisely for triangular pseudoline arrangements, one element of the image pair of f is a triangular complete-graph embedding on a surface. We obtain all triangular complete-graph embeddings on surfaces this way, when we extend the definition of triangular complete pseudoline arrangements in a natural way to that of triangular curve arrangements on surfaces in which each pair of curves has a point in common where they cross. Thus Ringel's results on the triangular complete-graph embeddings can be interpreted as results on curve arrangements on surfaces. Furthermore, we establish the relationship between 2-colorable curve arrangements and Petrie dual maps. A data structure, called intersection pattern is provided for the study of curve arrangements on surfaces. Finally we show that an orientable surface of genus g admits a complete curve arrangement with at most 2g+1 curves in contrast to the non-orientable surface where the number of curves is not bounded.     

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.     

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.     

类圈图的亏格分布

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

三维空间型中闭曲面和测地球面的比较

本文建立关于三维空间型中的可定向闭曲面的某些公式.引入积分绝对平均曲率来描述可定向闭曲面的平均弯曲程度.在此意义上,可定向闭曲面可以与作为包含该闭曲面的凸的测地球的边界测地球面进行比较,这种比较能用于说明空间型自身的某些属性     

A Polynomial Invariant of Graphs On Orientable Surfaces

We consider cyclic graphs, that is, graphs with cyclic ordersat the vertices, corresponding to 2-cell embeddings of graphsinto orientable surfaces, or combinatorial maps. We constructa three variable polynomial invariant of these objects, thecyclic graph polynomial, which has many of the useful propertiesof the Tutte polynomial. Although the cyclic graph polynomialgeneralizes the Tutte polynomial, its definition is very different,and it depends on the embedding in an essential way. 2000 MathematicalSubject Classification: 05C10.     

Genus embeddings for some complete tripartite graphs

The voltage graph construction of Gross is extended to the case where the base graph is non-orientably embedded. An easily applied criterion is established for determining the orientability character of the derived embedding. These methods are then applied to derive both orientable and non-orientable genus embeddings for some families of complete tripartite graphs.     

A duality theorem for graph embeddings

A generalized type of graph covering, called a “Wrapped quasicovering” (wqc) is defined. If K, L are graphs dually embedded in an orientable surface S, then we may lift these embeddings to embeddings of dual graphs K?,L? in orientable surfaces S?, such that S? are branched covers of S and the restrictions of the branched coverings to K?,L? are wqc's of K, L. the theory is applied to obtain genus embeddings of composition graphs G[nK₁] from embeddings of “quotient” graphs G.     

局部大边宽嵌入图的面圈和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...     

Closed 2-cell embeddings in the projective plane

An embedding of a multi-graph in a manifold is a closed 2-cell embedding provided the closures of the faces are all closed 2-cells. In this paper we characterized the projective planar multi-graphs that have closed 2-cell embeddings in the projective plane.