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.     

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

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

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).     

极大外平面图的不可定向强最大亏格

强嵌入猜想称:任意2-连通图都可以强嵌入到某一曲面上．本文通过分析极大外平面图的结构以及强嵌入的特征,讨论了该图类的不可定向强最大亏格,并给出了一个复杂度为O(nlogn)的算法．其中部分图类的强最大亏格嵌入提供该图的一个少双圈覆盖．     

Enumerative Properties of Rooted Circuit Maps

In 1966, Barnette introduced a set of graphs, called circuit graphs, which are obtained from 3-connected planar graphs by deleting a vertex. Circuit graphs and 3-connected planar graphs share many interesting properties which are not satisfied by general 2-connected planar graphs. Circuit graphs have nice closure properties which make them easier to deal with than 3-connected planar graphs for studying some graph-theoretic properties. In this paper, we study some enumerative properties of circuit graphs. For enumeration purpose, we define rooted circuit maps and compare the number of rooted circuit maps with those of rooted 2-connected planar maps and rooted 3-connected planar maps.     

Planar graphs with no 6-wheel minor

Tutte's wheels theorem states that the k-spoked wheel graphs, W_k, are the basic building blocks for the collection of simple, 3-connected graphs. Therefore it is of interest to examine the structure of the graphs that do not have a minor isomorphic to W_k for small values of k. Dirac determined that the graphs having no W₃-minor are the series-parallel networks. An easy consequence of Tutte's wheels theorem is that W₃ is the only simple, 3-connected graph that has a W₃-minor and no W₄-minor. Oxley characterized the graphs that have a W₄-minor and no W₅-minor. This paper characterizes the planar graphs that have a W₅-minor and no W₆-minor. A best-possible upper bound on the number of edges of such a graph is also determined.     

Cycle Covers of Planar 2-Edge-Connected Graphs

A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.     

3连通平面图的可去边数

设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。     

CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE

Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.     

Bounding the Size of Equimatchable Graphs of Fixed Genus

A graph G is said to be equimatchable if every matching in G extends to (i.e., is a subset of) a maximum matching in G. In an earlier paper with Saito, the authors showed that there are only a finite number of 3-connected equimatchable planar graphs. In the present paper, this result is extended by showing that in a surface of any fixed genus (orientable or non-orientable), there are only a finite number of 3-connected equimatchable graphs having a minimal embedding of representativity at least three. (In fact, if the graphs considered are non-bipartite, the representativity three hypothesis may be dropped.) The proof makes use of the Gallai-Edmonds decomposition theorem for matchings.      

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.     

Rigidity and Separation Indices of Graphs in Surfaces

Let Σ be a surface. We prove that rigidity indices of graphs which admit a polyhedral embedding in Σ and 5-connected graphs admitting an embedding in Σ are bounded by a constant depending on Σ. Moreover if the Euler characteristic of Σ is negative, then the separation index of graphs admitting a polyhedral embedding in Σ is also bounded. As a side result we show that distinguishing number of both Σ-polyhedral and 5-connected graphs which admit and embedding in Σ is also bounded.     

Cyclic coloration of 3-polytopes

A cyclic coloration of a planar graph G is an assignment of colors to the points of G such that for any face bounding cycle the points of F have different colors. We observe that the upper bound 2ρ*(G), due to O. Ore and M. D. Plummer, can be improved to ρ*(G) + 9 when G is 3-connected (ρ* denotes the size of a maximum face). The proof uses two principal tools: the theory of Euler contributions and recent results on contractible lines in 3-connected graphs by K. Ando, H. Enomoto and A. Saito.     

Shortness parameters of families of regular planar graphs with two or three types of face

This paper is concerned with non-Hamiltonian planar graphs. It is shown that the class of 3-connected cubic planar graphs whose faces are all pentagons or 10-gons contains non-Hamiltonian members and that the shortness coefficient of this class of graphs is less than unity. For several classes of 3-connected regular planar graphs, of valency 4 or 5, it is shown that the shortness exponent is less than unity.     

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.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

Hamiltonian properties of polyhedra with few 3-cuts—A survey

We give an overview of the most important techniques and results concerning the hamiltonian properties of planar 3-connected graphs with few 3-vertex-cuts. In this context, we also discuss planar triangulations and their decomposition trees. We observe an astonishing similarity between the hamiltonian behavior of planar triangulations and planar 3-connected graphs. In addition to surveying, (i) we give a unified approach to constructing non-traceable, non-hamiltonian, and non-hamiltonian-connected triangulations, and show that planar 3-connected graphs (ii) with at most one 3-vertex-cut are hamiltonian-connected, and (iii) with at most two 3-vertex-cuts are 1-hamiltonian, filling two gaps in the literature. Finally, we discuss open problems and conjectures.     

A Lower Bound on the Distortion of Embedding Planar Metrics into Euclidean Space

We exhibit a simple infinite family of series-parallel graphs that cannot be metrically embedded into Euclidean space with distortion smaller than

Schnyder Woods and Orthogonal Surfaces

In this paper we study connections between planar graphs, Schnyder woods, and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and the dimension theory of orders. Orthogonal surfaces explain connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says, that the face lattice of a 3-polytope minus one face has order dimension three. Our proof yields a linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondence with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder’s face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.     

Disjoint paths, planarizing cycles, and spanning walks

We study the existence of certain disjoint paths in planar graphs and generalize a theorem of Thomassen on planarizing cycles in surfaces. Results are used to prove that every 5-connected triangulation of a surface with sufficiently large representativity is hamiltonian, thus verifying a conjecture of Thomassen. We also obtain results about spanning walks in graphs embedded in a surface with large representativity.