Uniqueness of highly representative surface embeddings

Let Σ be a (connected) surface of “complexity” κ; that is, Σ may be obtained from a sphere by adding either ½κ handles or κ crosscaps. Let ρ ≥ 0 be an integer, and let Γ be a “ρ-representative drawing” in Σ; that is, a drawing of a graph in Σ so that every simple closed curve in Σ that meets the drawing in < ρ points bounds a disc in Σ. Now let Γ′ be another drawing, in another surface Σ′ of complexity κ′, so that Γ and Γ′ are isomorphic as abstract graphs. We prove that. (i) If ρ ≥ 100 log κ/ log log κ (or ρ ≥ 100 if κ ≤ 2) then κ′ ≥ κ, and if κ′ = κ and Γ is simple and 3-connected there is a homeomorphism from Σ to Σ′ taking Γ to Γ′, and. (ii) if Γ is simple and 3-connected and Γ′ is 3-representative, and ρ ≥ min (320, 5 log κ), then either there is a homeomorphism from Σ to Σ′ taking Γ to Γ′, or κ′ ≥ κ + 10^-4 ρ². © 1996 John Wiley & Sons, Inc.     

可定向曲面上具有较短不可收缩圈图嵌入的唯一性

拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作.     

Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs

Summary A variety of examples of 4-connected 4-regular graphs with no pair of disjoint Hamiltonian circuits were constructed in response to Nash-Williams conjecture that every 4-connected 4-regular graph is Hamiltonian and also admits a pair of edge-disjoint Hamiltonian circuits. Nash-Williams's problem is especially interesting for planar graphs since 4-connected planar graphs are Hamiltonian. Examples of 4-connected 4-regular planar graphs in which every pair of Hamiltonian circuits have edges in common are included in the above mentioned examples.B. Grünbaum asked whether 5-connected planar graphs always admit a pair of disjoint Hamiltonian circuits. In this paper we introduce a technique that enables us to construct infinitely many examples of 5-connected planar graphs, 5-regular and non regular, in which every pair of Hamiltonian circuits have edges in common.     

The maximal coarse Baum–Connes conjecture for spaces which admit a fibred coarse embedding into Hilbert space

We introduce a notion of fibred coarse embedding into Hilbert space for metric spaces, which is a generalization of Gromov?s notion of coarse embedding into Hilbert space. It turns out that a large class of expander graphs admit such an embedding. We show that the maximal coarse Baum–Connes conjecture holds for metric spaces with bounded geometry which admit a fibred coarse embedding into Hilbert space.     

Anosov diffeomorphisms on infra-nilmanifolds associated to graphs

Anosov diffeomorphisms on closed Riemannian manifolds are a type of dynamical systems exhibiting uniform hyperbolic behavior. Therefore, their properties are intensively studied, including which spaces allow such a diffeomorphism. It is conjectured that any closed manifold admitting an Anosov diffeomorphism is homeomorphic to an infra-nilmanifold, that is, a compact quotient of a 1-connected nilpotent Lie group by a discrete group of isometries. This conjecture motivates the problem of describing which infra-nilmanifolds admit an Anosov diffeomorphism. So far, most research was focused on the restricted class of nilmanifolds, which are quotients of 1-connected nilpotent Lie groups by uniform lattices. For example, Dani and Mainkar studied this question for the nilmanifolds associated to graphs, which form the natural generalization of nilmanifolds modeled on free nilpotent Lie groups. This paper further generalizes their work to the full class of infra-nilmanifolds associated to graphs, leading to a necessary and sufficient condition depending only on the induced action of the holonomy group on the defining graph. As an application, we construct families of infra-nilmanifolds with cyclic holonomy groups admitting an Anosov diffeomorphism, starting from faithful actions of the holonomy group on simple graphs.     

Closed 2-cell embeddings of graphs with no V8-minors

A closed 2-cell embedding of a graph embedded in some surface is an embedding such that each face is bounded by a cycle in the graph. The strong embedding conjecture says that every 2-connected graph has a closed 2-cell embedding in some surface. In this paper, we prove that any 2-connected graph without V₈ (the Möbius 4-ladder) as a minor has a closed 2-cell embedding in some surface. As a corollary, such a graph has a cycle double cover. The proof uses a classification of internally-4-connected graphs with no V₈-minor (due to Kelmans and independently Robertson), and the proof depends heavily on such a characterization.     

Pairs of Hamiltonian circuits in 5-connected planar graphs

Settling a problem raised by B. Grünbaum, J. Malkevitch, and the author, we present 5-valent 5-connected planar graphs that admit no pairs of edgedisjoint Hamiltonian circuits; our smallest example has 176 vertices. This is used to construct an infinite family of 5-valent 5-connected planar graphs, in which every member has the property that any pair of Hamiltonian circuits in it share at least about $\text{1}\text{168}$ of their edges. We construct 4- and 5-valent, 3-connected non-Hamiltonian planar graphs.     

Orientation embedding of signed graphs

A signed graph Σ consists of a graph and a sign labeling of its edges. A polygon in Σ is “balanced” if its sign product is positiive. A signed graph is “orientatio embedded” in a surface if it is topologically embedded and a polygon is balanced precisely when traveling once around it preserves orientation. We explore the extension to orientation embedding of the ordinary theory of graph embedding. Let d(Σ) be the demigenus (= 2 - x(S)) of the unique smallest surface S in which Σ has an orientation embedding. Our main results are an easy one, that if Σ has connected components Σ₁, Σ[2], ?, then d(Σ) = d(Σ₁) + ?, and a hard one, that if Σ has a cut vertex v that splits Σ into Σ₁, Σ₂, ?, then d(Σ) = d(Σ₁) + d(Σ₂) + ? -δ, where δ depends on the number of Σ_i in which v is “loopable”, that is, in which d(Σ_i) = d(Σ_{i with a negative loop added to v}). This is as with ordinary orientable grpah embedidng except for the existence of the term δ in the cut-vertex formula. Since loopability is crucial, we give some partial criteria for it. (A complete characterization seems difficult.) We conclude with an application to forbidden subgraphs and minors for orientation embeddability in a given surface. © 1929 John Wiley & Sons, Inc.     

Tessellation and Visibility Representations of Maps on the Torus

The model of the torus as a parallelogram in the plane with opposite sides identified enables us to define two families of parallel lines and to tessellate the torus, then to associate to each tessellation a toroidal map with an upward drawing. It is proved that a toroidal map has a tessellation representation if and only if its universal cover is 2-connected. Those graphs that admit such an embedding in the torus are characterized. Received November 22, 1995, and in revised form May 1, 1997.     

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.     

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.     

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.     

Weinberg bounds over nonspherical graphs

Let Aut(G) and E(G) denote the automorphism group and the edge set of a graph G, respectively. Weinberg's Theorem states that 4 is a constant sharp upper bound on the ratio |Aut(G)|/|E(G)| over planar (or spherical) 3‐connected graphs G. We have obtained various analogues of this theorem for nonspherical graphs, introducing two Weinberg‐type bounds for an arbitrary closed surface Σ, namely: where supremum is taken over the polyhedral graphs G with respect to Σ for W_P(Σ) and over the graphs G triangulating Σ for W_T(Σ). We have proved that Weinberg bounds are finite for any surface; in particular: W_P = W_T = 48 for the projective plane, and W_T = 240 for the torus. We have also proved that the original Weinberg bound of 4 holds over the graphs G triangulating the projective plane with at least 8 vertices and, in general, for the graphs of sufficiently large order triangulating a fixed closed surface Σ. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 220–236, 2000     

On the edge reconstruction of graphs embedded on surfaces

In this paper, we proved that ifG is a 3-connected graph of minimum valency δ = 6χ + 5 with α a non-negative integer and if there exists an embedding ψ ofG on a surface Σ of characteristic ?(Σ) = — α|V(G)∣+ β with the representativity of the embedding ψ ≥ 3, where ψ ε 0,1, thenG is edge reconstructible.     

Concept of a vertex in a matroid and 3-connected graphs

The concept of a matroid vertex is introduced. The vertices of a matroid of a 3-connected graph are in one-to-one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3-connected graphs implies isomorphism. The concept of a vertex of a matroid leads to an equally simple proof of Whitney's theorem on the unique embedding of a 3-connected planar graph in the sphere. It also leads to a number of new facts about 3-connected graphs. Thus, consideration of a vertex in a matroid that is the dual of the matroid of a graph leads to a natural concept of a nonseparating cycle of a graph. Whitney's theorem on cyclic isomorphism can be strengthened (even if the nonseparating cycles of a graph are considered, the theorem is found to work) and a new criterion for planarity of 3-connected graphs is obtained (in terms of nonseparating cycles).     

Bimatroidal independence systems

An independence system Σ=(X, F) is called bimatroidal if there exist two matroidsM=(X F _M) andN=(X, F _N) such thatF=F _M∪ F_N. When this is the case, {M,N} is called a bimatroidal decomposition of Σ. This paper initiates the study of bimatroidal systems. Given the collection of circuits of an arbitrary independence system Σ (or, equivalently, the constraints of a set-covering problem), we address the following question: does Σ admit a bimatroidal decomposition {M,N} and, if so, how can we actually produce the circuits ofM andN? We derive a number of results concerning this problem, and we present a polynomial time algorithm to solve it when every two circuits of Σ have at most one common element. We also propose different polynomial time algorithms for set covering problems defined on the circuit-set of bimatroidal systems.     

Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface

A polyhedral embedding in a surface is one in which any two faces have boundaries that are either disjoint or simply connected. In a cubic (3-regular) graph this is equivalent to the dual being a simple graph. In 1968, Grünbaum conjectured that every cubic graph with a polyhedral embedding in an orientable surface is 3-edge-colorable. For the sphere, this is equivalent to the Four-Color Theorem, but we have disproved the conjecture in the general form. In this paper we extend this result and show that if we restrict our attention to a class of cubic graphs with a polyhedral embedding in an orientable surface, then the computational complexity of the 3-edge-coloring problem and its approximation does not improve.     

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.     

The 3-connected graphs having a longest cycle containing only three contractible edges

It is shown that with one small exception, the 3-connected graphs admitting longest cycles that contain less than four contractible edges of the parent graph are the members of three closely related infinite families. © 1993 John Wiley & Sons, Inc.     

Vertex-transitive graphs: Symmetric graphs of prime valency

Let G be a group acting symmetrically on a graph Σ, let G₁ be a subgroup of G minimal among those that act symmetrically on Σ, and let G₂ be a subgroup of G₁ maximal among those normal subgroups of G₁ which contain no member except 1 which fixes a vertex of Σ. The most precise result of this paper is that if Σ has prime valency p, then either Σ is a bipartite graph or G₂ acts regularly on Σ or G₁ | G₂ is a simple group which acts symmetrically on a graph of valency p which can be constructed from Σ and does not have more vertices than Σ. The results on vertex-transitive groups necessary to establish results like this are also included.