A structural theorem on embedded graphs and its application to colorings

In this paper, a Lebesgue type theorem on the structure of graphs embedded in the surface of characteristic σ≤ 0 is given, that generalizes a result of Borodin on plane graphs. As a consequence, it is proved that every such graph without i-circuits for 4 ≤ i ≤ 11 - 3σ is 3-choosable, that offers a new upper bound to a question of Y. Zhao.     

Boolean planarity characterization of graphs

Although many criteria for testing the planarity of a graph have been found since the beginning of the thirties, this paper presents a new criterion described by Boolean technique which is proved in an independent way without any use of the criteria obtained before. This research was supported by the U.S. National Science Foundation under Grant Number ECS 85 03212 and by the National Natural Science Foundation of China as well. And, the author is greatly indebted to Professor Peter L. Hammer for many helpful discussions, suggestions, and comments.     

A strengthening of the Kuratowski planarity criterion for 3-connected graphs

We prove that any non-planar 3-connected graph with at least 6 vertices contains a cycle with three pairwise ‘interwoven’ chords.     

Characterizing planarity using theta graphs

A theta graph is a homeomorph of K_2,3. In an embedded planar graph the local rotation at one degree-three vertex of a theta graph determines the local rotation at the other degree-three vertex. Using this observation, we give a characterization of planar graphs in terms of balance in an associated signed graph whose vertices are K_1,3 subgraphs and whose edges correspond to theta graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 17–20, 1998     

On the planarity of jump graphs

For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph J_k(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of J_k(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J₂(G) is planar are determined.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

A Ramsey-type theorem for traceable graphs

A graph G is traceable if there is a path passing through all the vertices of G. It is proved that every infinite traceable graph either contains arbitrarily large finite chordless paths, or contains a subgraph isomorphic to graph A, illustrated in the text. A corollary is that every finitely generated infinite lattice of length 3 contains arbitrarily large finite fences. It is also proved that every infinite traceable graph containing no chordless four-point path contains a subgraph isomorphic to K_ω,ω. The versions of these results for finite graphs are discussed.     

A uniqueness theorem for Delaunay graphs

We establish a necessary and sufficient condition for the congruence of two isomorphic Delaunay graphs.     

A Penrose polynomial for embedded graphs

We extend the Penrose polynomial, originally defined only for plane graphs, to graphs embedded in arbitrary surfaces. Considering this Penrose polynomial of embedded graphs leads to new identities and relations for the Penrose polynomial which cannot be realized within the class of plane graphs. In particular, by exploiting connections with the transition polynomial and the ribbon group action, we find a deletion–contraction-type relation for the Penrose polynomial. We relate the Penrose polynomial of an orientable chequerboard colourable graph to the circuit partition polynomial of its medial graph and use this to find new combinatorial interpretations of the Penrose polynomial. We also show that the Penrose polynomial of a plane graph G$G$ can be expressed as a sum of chromatic polynomials of twisted duals of G$G$. This allows us to obtain a new reformulation of the Four Colour Theorem.     

On the planarity of Hanoi graphs

Hanoi graphs are the state graphs for Tower of Hanoi problems with three or more pegs. We prove hamiltonicity and present a complete analysis of planarity of these graphs.     

A dirac-type theorem for squares of graphs

We prove that if G is a connected graph with p vertices and minimum degree greater than max (p/4 ? 1,3) then G² is pancyclic. The result is best possible of its kind.     

A Helly theorem for convexity in graphs

It is shown that for chordless path convexity in any graph, the Helly number equals the size of a maximum clique.     

A Bernstein theorem for special Lagrangian graphs

We obtain a Bernstein theorem for special Lagrangian graphs in for arbitrary n only assuming bounded slope but no quantitative restriction. Received: 18 January 2001 / Accepted: 7 June 2001 / Published online: 12 October 2001 The second-named author is grateful to the Max Planck Institute for Mathematics in the Sciences in Leipzig for its hospitality and support and also 973 project in China.     

A min-max theorem for plane bipartite graphs

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621-1625].     

A new approach to the linearity of testing planarity of graphs

In testing planarity of graphs, there are many criteria. The earliest one as known is the Kuratowski's theorem, then Whitney's, Maclane's, and so forth. Since the early sixties, people have begun researches on algorithms. Up to 1974, Hopcroft and Tarjan found an algorithm with a computing time being a linear function of the order of a graph. This is the linearity concerned here.This paper presents a new approach to the linearity by means of transforming the problem of testing planarity of a graphG into that of finding a spanning tree on another graphH, called an auxiliary graph ofG, with the order ofH being a linear function of that ofG. And moreover, we can also make the size ofH be a linear function of that ofG. The whole procedure is based on the building up of a theory of linear equations onGF (2) related toG.This was a report invited by RUTCOR, The State University of New Jersey, Rutgers, U. S. A. in 1984. And, the main part of this paper was completed during the author's stay at the Department of C & O, University of Waterloo, Canada.     

A separator theorem for graphs of bounded genus

Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful classes do. One such class is planar graphs: If an n-vertex graph can be drawn on the plane, then it can be bisected by removal of O(sqrt(n)) vertices (R. J. Lipton and R. E. Tarjan, SIAM J. Appl. Math.36 (1979), 177–189). The main result of the paper is that if a graph can be drawn on a surface of genus g, then it can be bisected by removal of O(sqrt(gn)) vertices. This bound is best possible to within a constant factor. An algorithm is given for finding the separator that takes time linear in the number of edges in the graph, given an embedding of the graph in its genus surface. Some extensions and applications of these results are discussed.