Small Drawings of Outerplanar Graphs,Series-Parallel Graphs,and Other Planar Graphs

In this paper, we study small planar drawings of planar graphs. For arbitrary planar graphs, Θ(n ²) is the established upper and lower bound on the worst-case area. A long-standing open problem is to determine for what graphs a smaller area can be achieved. We show here that series-parallel graphs can be drawn in O(n ^3/2) area, and outerplanar graphs can be drawn in O(nlog n) area, but 2-outerplanar graphs and planar graphs of proper pathwidth 3 require Ω(n ²) area. Our drawings are visibility representations, which can be converted to polyline drawings of asymptotically the same area.     

Graph Sandwich Problems

The graph sandwich problem for property Π is defined as follows: Given two graphs G¹ = (V, E¹) and G² = (V, E²) such that E¹ E², is there a graph G = (V, E) such that E¹ E E² which satisfies property Π? Such problems generalize recognition problems and arise in various applications. Concentrating mainly on properties characterizing subfamilies of perfect graphs, we give polynomial algorithms for several properties and prove the NP-completeness of others. We describe polynomial time algorithms for threshold graphs, split graphs, and cographs. For the sandwich problem for threshold graphs, the only case in which a previous algorithm existed, we obtain a faster algorithm. NP-completeness proofs are given for comparability graphs, permutation graphs, and several other families. For Eulerian graphs; one Version of the problem is polynomial and another is NP-complete.     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

Extensions of the duality between minimal surfaces and maximal surfaces

As a generalization of the classical duality between minimal graphs in E ³ and maximal graphs in L ³, we construct the duality between graphs of constant mean curvature H in Bianchi-Cartan-Vranceanu space E ³(κ, τ) and spacelike graphs of constant mean curvature τ in Lorentzian Bianchi-Cartan-Vranceanu space L ³(κ, H).     

Families of Graphs Closed Under Taking Powers

 This paper gives simple proofs for “G ^k ∈? implies G ^{k +1}∈?” when ? is the family of all interval graphs, all proper interval graphs, all cocomparability graphs, or all m-trapezoid graphs. Received: November 21, 1997 Final version received: October 5, 1998     

Half-Transitive Graphs of Prime-Cube Order

We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p ³ and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p ³ and exponent p ², and up to isomorphism there are exactly (p – 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.     

Improved boolean formulas for the Ramsey graphs

In the theory of the random graphs, there are properties of graphs such that almost all graphs satisfy the property, but there is no effective way to find examples of such graphs. By the well-known results of Razborov, for some of these properties, e.g., some Ramsey property, there are Boolean formulas in ACC representing the graphs satisfying the property and having exponential number of vertices with respect to the number of variables of the formula. Razborov's proof is based on a probabilistic distribution on formulas of n variables of size approximately nd² log d, where d is a polynomial in n, and depth 3 in the basis { ∧, ⊕} with the following property: The restriction of the formula randomly chosen from the distribution to any subset A of the Boolean cube {0, 1}ⁿ of size at most d has almost uniform distribution on the functions A → {0, 1}. We show a modified probabilistic distribution on Boolean formulas which is defined on formulas of size at most nd log² d and has the same property of the restrictions to sets of size at most d as the original one. This allows us to obtain formulas the complexity of which is a polynomial of a smaller degree in n than in Razborov's paper while the represented graphs satisfy the same properties.     

Finding a Sun in Building-Free Graphs

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156–2162, 2010). We show that whether a building-free graph contains a sun can be decided in O(min{mn ³, m ^1.5 n ²}) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.     

Uncontractable 4-connected graphs

The only uncontractable 4-connected graphs are C²_n for n ≥ 5 and the line graphs of the cubic cyclically 4-connected graphs.     

Alternating cycle-free matchings

The investigation of alternating cycle-free matchings is motivated by the Jump-number problem for partially ordered sets and the problem of counting maximum cardinality matchings in hexagonal systems.We show that the problem of deciding whether a given chordal bipartite graph has an alternating cycle-free matching of a given cardinality is NP-complete. A weaker result, for bipartite graphs only, has been known for some time. Also, the alternating cycle-free matching problem remains NP-complete for strongly chordal split graphs of diameter 2.In contrast, we give algorithms to solve the alternating cycle-free matching problem in polynomial time for bipartite distance hereditary graphs (time O(m ²) on graphs with m edges) and distance hereditary graphs (time O(m ⁵)).     

Edge‐decompositions of Kn,n into isomorphic copies of a given tree

We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These n × n bipartite graphs provide constructions of C₆‐free graphs with Ω(n^4/3 edges, C₁₀‐free graphs with Ω(n^6/5) edges, and Θ(7,7,7)‐free graphs with Ω(n^8/7) edges. Each of these bounds is sharp in order of magnitude. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 1–10, 2005     

Intersection Graphs and the Clique Operator

 Let P be a class of finite families of finite sets that satisfy a property P. We call ΩP the class of intersection graphs of families in P and CliqueP the class of graphs whose family of cliques is in P. We prove that a graph G is in ΩP if and only if there is a family of complete sets of G which covers all edges of G and whose dual family is in P. This result generalizes that of Gavril for circular-arc graphs and conduces those of Fulkerson-Gross, Gavril and Monma-Wei for interval graphs, chordal graphs, UV, DV and RDV graphs. Moreover, it leads to the characterization of Helly-graphs and dually chordal graphs as classes of intersection graphs. We prove that if P is closed under reductions, then CliqueP=Ω(P ^*∩H) (P ^*= Class of dual families of families in P). We find sufficient conditions for the Clique Operator, K, to map ΩP into ΩP ^*. These results generalize several known results for particular classes of intersection graphs. Furthermore, they lead to the Roberts-Spencer characterization for the image of K and the Bandelt-Prisner result on K-fixed classes. Received: August 18, 1997 Final version received: March 30, 1999     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.     

Embeddings on a boolean cube

In this paper, we characterize a class of graphs which can be embedded on a boolean cube. Some of the graphs in this class are identified with the well known graphs such asmulti-dimensional mesh of trees, tree of meshes, etc. We suggest (i) an embedding of anr-dimensional mesh of trees ofn ^r (r+1)–rn ^r–1 nodes on a boolean cube of (2n) ^r nodes, and (ii) an embedding of a tree of meshes with 2n ² logn+n ² nodes on a boolean cube withn ² exp₂ (log (2 logn+1)]) nodes.     

A Family of Antipodal Distance-Regular Graphs Related to the Classical Preparata Codes

A new family of distance-regular graphs is constructed. They are antipodal 2^2t–1-fold covers of the complete graph on 2^2t vertices. The automorphism groups are determined, and the extended Preparata codes are reconstructed using walks on these graphs.There are connections to other interesting structures: the graphs are equivalent to certain generalized Hadamard matrices; and their underlying 3-class association scheme is formally dual to the scheme of a system of linked symmetric designs obtained from Kerdock sets of skew matrices in characteristic two.     

Perfect and locally perfect colorings

We present a new algorithm for coloring perfect graphs and use it to color the parity orderable graphs, a class which strictly contains parity graphs. Also, we modify this algorithm to obtain an O(m² + n) locally perfect coloring algorithm for parity graphs. © 1995 John Wiley & Sons, Inc.     

On the Determination Problem for P 4-Transformation of Graphs

We prove that the P ₄-transformation is one-to-one on the set of graphs with minimum degree at least 3, and if graphs G and G ^' have minimum degree at least 3 then any isomorphism from the P ₄-graph P ₄(G) to the P ₄-graph P ₄(G ^') is induced by a vertex-isomorphism from G to G ^' unless G and G ^' both belong to a special family of graphs. Supported by NSFC, PCSIRT and the “973” program.     

Symmetry of iteration graphs

We examine iteration graphs of the squaring function on the rings ℤ/nℤ when n = 2 ^k p, for p a Fermat prime. We describe several invariants associated to these graphs and use them to prove that the graphs are not symmetric when k = 3 and when k ⩾ 5 and are symmetric when k = 4.     

Sparse graphs: Metrics and random models

Recently, Bollobás, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with n vertices and Θ(n) edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function κ: [0, 1]² → [0, ∞). To understand these models, we should like to know when different kernels κ give rise to “similar” graphs, and, given a real‐world network, how “similar” is it to a typical graph G(n, κ) derived from a given kernel κ. The analogous questions for dense graphs, with Θ(n²) edges, are answered by recent results of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in [0, 1]. Possible generalizations of these results to graphs with o(n²) but ω(n) edges are discussed in a companion article [Bollobás and Riordan, London Math Soc Lecture Note Series 365 (2009), 211–287]; here we focus only on graphs with Θ(n) edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models and vice versa. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 1‐38, 2011