Connectivity of iterated line graphs

Let k≥0 be an integer and L^k(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L²(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L²(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.     

Flips in planar graphs

We review results concerning edge flips in planar graphs concentrating mainly on various aspects of the following problem: Given two different planar graphs of the same size, how many edge flips are necessary and sufficient to transform one graph into another? We overview both the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight the similarities and differences of the two settings, describe many extensions and generalizations, highlight algorithmic issues, outline several applications and mention open problems.     

Connectivity and design of planar global attractors of Sturm type. II: Connection graphs

Based on a Morse-Smale structure we study planar global attractors Af of the scalar reaction-advection-diffusion equation ut=uxx+f(x,u,ux) in one space dimension. We assume Neumann boundary conditions on the unit interval, dissipativeness of f, and hyperbolicity of equilibria. We call Af Sturm attractor because our results strongly rely on nonlinear nodal properties of Sturm type.The planar Sturm attractor consists of equilibria of Morse index 0, 1, or 2, and their heteroclinic connecting orbits. The unique heteroclinic orbits between adjacent Morse levels define a plane graph Cf which we call the connection graph. Its 1-skeleton consists of the unstable manifolds (separatrices) of the index-1 Morse saddles.We present two results which completely characterize the connection graphs Cf and their 1-skeletons in purely graph theoretical terms. Connection graphs are characterized by the existence of pairs of Hamiltonian paths with certain chiral restrictions on face passages. Their 1-skeletons are characterized by the existence of cycle-free orientations with certain restrictions on their criticality. Such orientations are called bipolar in [H. de Fraysseix, P.O. de Mendez, P. Rosenstiehl, Bipolar orientations revisited, Discrete Appl. Math. 56 (1995) 157-179].In [B. Fiedler, C. Rocha, Connectivity and design of planar global attractors of Sturm type. I: Orientations and Hamiltonian paths, Crelle J. Reine Angew. Math. (2007), in press] we have shown the equivalence of the two characterizations. Moreover we have established that connection graphs of Sturm attractors indeed satisfy the required properties. In the present paper we show, conversely, how to design a planar Sturm attractor with prescribed plane connection graph or 1-skeleton of the required properties. In [B. Fiedler, C. Rocha, Connectivity and design of planar global attractors of Sturm type. III: Small and Platonic examples, 2007, submitted for publication] we describe all planar Sturm attractors with up to 11 equilibria. We also design planar Sturm attractors with prescribed Platonic 1-skeletons.     

Straight line embeddings of cubic planar graphs with integer edge lengths

We prove that every simple cubic planar graph admits a planar embedding such that each edge is embedded as a straight line segment of integer length. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:270‐274, 2008     

Connectivity measures in matched sum graphs

A matched sum graph G of two graphs G₁ and G₂ of the same order is obtained from the union of G₁ and G₂ and from joining each vertex of G₁ with one vertex of G₂ according to one bijection f between the vertices in V(G₁) and V(G₂). When G₁=G₂=H then f is just a permutation of V(H) and the corresponding matched sum graph is a permutation graph H^f. In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities.     

Extremal graphs in connectivity augmentation

Let A(n, k, t) denote the smallest integer e for which every k‐connected graph on n vertices can be made (k + t)‐connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999     

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

-Linked planar graphs

A graph G is (m,n)-linked if for any two disjoint subsets R,BV(G) with |R|m and |B|n, G has two disjoint connected subgraphs containing R and B, respectively. We shall prove that a planar graph with at least six vertices is (3,3)-linked if and only if G is 4-connected and maximal.     

Orienting planar graphs

It is shown that every maximal planar graph (triangulation) can be contracted at an arbitrary point (by identifying it with an adjacent point) so that triangularity is preserved. This is used as a lemma to prove that every triangulation can be (a) oriented so that with three exceptions every point has indegree three, the exceptions having indegrees 0, 1 and 2, and (b) decomposed into three edge-disjoint trees of equal order. The lemma also provides an elementary proof of a theorem of Wagner that every triangulation can be represented by a straight-line drawing.     

Connectivity of inhomogeneous random graphs

We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when . We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i, j) is added with probability , where is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 408‐420, 2014     

Connectivity of Cartesian product graphs

Use v_i,κ_i,λ_i,δ_i to denote order, connectivity, edge-connectivity and minimum degree of a graph G_i for i=1,2, respectively. For the connectivity and the edge-connectivity of the Cartesian product graph, up to now, the best results are κ(G₁×G₂)?κ₁+κ₂ and λ(G₁×G₂)?λ₁+λ₂. This paper improves these results by proving that κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁} and λ(G₁×G₂)=min{δ₁+δ₂,λ₁v₂,λ₂v₁} if G₁ and G₂ are connected undirected graphs; κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁,2κ₁+κ₂,2κ₂+κ₁} if G₁ and G₂ are strongly connected digraphs. These results are also generalized to the Cartesian products of connected graphs and n strongly connected digraphs, respectively.     

Connectivity threshold of Bluetooth graphs

We study the connectivity properties of random Bluetooth graphs that model certain “ad hoc” wireless networks. The graphs are obtained as “irrigation subgraphs” of the well‐known random geometric graph model. There are two parameters that control the model: the radius r that determines the “visible neighbors” of each vertex and the number of edges c that each vertex is allowed to send to these. The randomness comes from the underlying distribution of vertices in space and from the choices of each vertex. We prove that no connectivity can take place with high probability for a range of parameters r, c and completely characterize the connectivity threshold (in c) for values of r close the critical value for connectivity in the underlying random geometric graph.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 45–66, 2014     

Coloring planar graphs in parallel

We present NC algorithms for vertex and edge coloring planar graphs. The vertex coloring algorithm 5 colors any planar graph, and the edge coloring algorithm Δ edge colors planar graphs with Δ ≥ 23 (and Δ + 1 edge colors planar graphs with Δ < 23), where Δ is the maximum degree in the graph.     

Even circuits in planar graphs

We prove that a planar graph can be partitioned into edge-disjoint circuits of even length, if and only if every vertex has even valency and every block has an even number of edges.     

Nested hierarchies in planar graphs

We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named ‘bubbles’, that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tree structure where neighboring bubbles are joined together by a 3-clique. Bubbles naturally provide the subdivision of G into communities and the tree structure defines the hierarchical relations between these communities.