Mutation on knots and Whitney’s 2-isomorphism theorem

Whitney’s 2-switching theorem states that any two embeddings of a 2-connected planar graph in S ² can be connected via a sequence of simple operations, named 2-switching. In this paper, we obtain two operations on planar graphs from the view point of knot theory, which we will term “twisting” and “2-switching” respectively. With the twisting operation, we give a pure geometrical proof of Whitney’s 2-switching theorem. As an application, we obtain some relationships between two knots which correspond to the same signed planar graph. Besides, we also give a necessary and sufficient condition to test whether a pair of reduced alternating diagrams are mutants of each other by their signed planar graphs.     

Uniqueness and faithfulness of embedding of toroidal graphs

A topological generalization of the uniqueness of duals of 3-connected planar graphs will be obtained. A graph G is uniquely embeddable in a surface F if for any two embeddings $\text{?}{}_1$, $\text{?}{}_2\text{:G → F}$, there are an autohomeomorphism h:F → F and an automorphism σ:G → G such that $\text{h°?}{}_1\text{= ?}{}_2\text{°σ}$. A graph G is faithfully embedabble in a surface F if there is an embedding $\text{?:G → F}$ such that for any automorphism σ:G → G, there is an autohomeomorphism h:F → F with $\text{h°? = f°σ}$. Our main theorems state that any 6-connected toroidal graph is uniquelly embeddable in a torus and that any 6-connected toroidal graph with precisely three exceptions is faithfully embeddable in a torus. The proofs are based on a classification of 6-regular torus graphs.     

The reconstruction of separable graphs with 2-connected trunks that are series-parallel networks

A 2-connected graph has a cleavage unit-virtual edge decomposition which is due to Tutte [8]. Cleavage units are either polygons, bonds (planar duals to polygons) or 3-connected simple graphs. When all cleavage units are polygons or bonds, such graphs are called series-parallel networks. The Ulam graph reconstruction conjecture is open for the class of connected graphs containing circuits and/or pendant vertices. Such graphs can be expressed uniquely in terms of a trunk, a connected subgraph without pendant vertices, and a tree-growth, a forest each connected component of which meets the trunk in a unique root vertex. This paper establishes the reconstruction conjecture when the trunk is a series-parallel network and the tree-growth is ‘non-trivial’. This is accomplished by means of Tutte's decomposition of the trunk, and group theoretical techniques first developed in [2]. Use is made of the restricted nature of the automorphism groups of the polygon and bond cleavage units of the trunk.     

Generating planar 4-connected graphs

In this paper, we introduce three operations on planar graphs that we call face splitting, double face splitting, and subdivision of hexagons. We show that the duals of the planar 4-connected graphs can be generated from the graph of the cube by these three operations. That is, given any graphG that is the dual of a planar 4-connected graph, there is a sequence of duals of planar 4-connected graphsG ₀,G ₁, …,G _n such thatG ₀ is the graph of the cube,G _n=G, and each graph is obtained from its predecessor by one of our three operations. Research supported by a Sloan Foundation fellowship and by NSF Grant#GP-27963.     

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.     

Geodesic Embeddings and Planar Graphs

Schnyder labelings are known to have close links to order dimension and drawings of planar graphs. It was observed by Ezra Miller that geodesic embeddings of planar graphs are another class of combinatorial or geometric objects closely linked to Schnyder labelings. We aim to contribute to a better understanding of the connections between these objects. In this article we prove • a characterization of 3-connected planar graphs as those graphs admitting rigid geodesic embeddings, • a bijection between Schnyder labelings and rigid geodesic embeddings, • a strong version of the Brightwell–Trotter theorem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bounding the number of embeddings of 5-connected projective-planar graphs

A graph is said to be projective-planar if it is nonplanar and is embeddable in a projective plane. In this paper we show that the numbers of projectiveplanar embeddings (up to equivalence) of all 5-connected graphs have an upper bound c(?120).     

Uniquely and faithfully embeddable projective-planar triangulations

Let G be a 5-connected graph not isomorphic to the complete graph K₆ with 6 vertices and triangularly embedded in a projective plane P². Then it will be shown that for any embedding f: G → P², there is a homeomorphism h: P² → P² such that h| G = f. In our terminology, the result states that every 5-connected projective-planar triangulation is uniquely and faithfully embeddable in a projective plane unless it is isomorphic to K₆.     

Graphs of given genus and arbitrarily large maximum genus

The maximum genus of a connected graph G is the maximum among the genera of all compact orientable 2-manifolds upon which G has 2-cell embeddings. In the theorems that follow the use of an edge-adding technique is combined with the well-known Edmonds' technique to produce the desired results. Planar graphs of arbitrarily large maximum genus are displayed in Theorem 1. Theorem 2 shows that the possibility for arbitrarily large difference between genus and maximum genus is not limited to planar graphs. In particular, we show that the wheel graph, the standard maximal planar graph, and the prism graph are upper embeddable. We then show that given m and n, there is a graph of genus n and maximum genus larger than mn.     

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

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

Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs

In 1956, W.T. Tutte proved that every 4-connected planar graph is hamiltonian. Moreover, in 1997, D.P. Sanders extended this to the result that a 4-connected planar graph contains a hamiltonian cycle through any two of its edges. It is shown that Sanders’ result is best possible by constructing 4-connected maximal planar graphs with three edges a large distance apart such that any hamiltonian cycle misses one of them. If the maximal planar graph is 5-connected then such a construction is impossible.     

A Characterization of Graphs with No Cube Minor

In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor of the line graph of V_n for some n6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-connected graph with a vertex of degree at least 8 with no cube minor. Further, it is shown that any graph with no cube minor is obtained from 4-connected such graphs by 0-, 1-, and 2-summing, and 3-summing over a specified triangles.     

Large non-planar graphs and an application to crossing-critical graphs

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K4,k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

Random graphs on surfaces

Counting labelled planar graphs, and typical properties of random labelled planar graphs, have received much attention recently. We start the process here of extending these investigations to graphs embeddable on any fixed surface S. In particular we show that the labelled graphs embeddable on S have the same growth constant as for planar graphs, and the same holds for unlabelled graphs. Also, if we pick a graph uniformly at random from the graphs embeddable on S which have vertex set {1,…,n}, then with probability tending to 1 as n→∞, this random graph either is connected or consists of one giant component together with a few nodes in small planar components.     

Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.     

Thickness and outerthickness for embedded graphs

We prove new upper bounds for the thickness and outerthickness of a graph in terms of its orientable and nonorientable genus by applying the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness. We also show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This implies that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. Finally, we show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5.     

Isometric embedding in products of complete graphs

An isometric (i.e., distance-preserving) embedding of a connected graph G into a cartesian product of complete graphs is equivalent to a labelling of each vertex of G by a string of symbols of fixed length such that the distance between two vertices is equal to the Hamming distance between the corresponding strings. Such a labelling could provide an addressing scheme for a communications network, since it enables a message to find a shortest path to its destination using only local information.We show that any two such embeddings of the same graph G are essentially the same, and give a polynomial-time algorithm which will find such an embedding if it exists. In addition we characterize the graphs which are isometrically embeddable in powers of K₃.     

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.     

On encodings of spanning trees

Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n₁,…,n_r). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues.