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.     

Graph factors and factorization: 1985–2003: A survey

In the most general sense, a factor of a graph G is just a spanning subgraph of G and a graph factorization of G is a partition of the edges of G into factors. However, as we shall see in the present paper, even this extremely general definition does not capture all the factor and factorization problems that have been studied in graph theory. Several previous survey papers have been written on this subject [F. Chung, R. Graham, Recent results in graph decompositions, London Mathematical Society, Lecture Note Series, vol. 52, Cambridge University Press, 1981, pp. 103–123; J. Akiyama, M. Kano, Factors and factorizations of graphs—a survey, J. Graph Theory 9 (1985) 1–42; L. Volkmann, Regular graphs, regular factors, and the impact of Petersen's theorems, Jahresber. Deutsch. Math.-Verein. 97 (1995) 19–42] as well as an entire book on graph decompositions [J. Bosák, Decompositions of Graphs, Kluwer Academic Publishers Group, Dordrecht, 1990]. Our purpose here is to concentrate primarily on surveying the developments of the last 15–20 years in this exponentially growing field.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

Symplectically hyperbolic manifolds

A symplectic form is called hyperbolic if its pull-back to the universal cover is a differential of a bounded one-form. The present paper is concerned with the properties and constructions of manifolds admitting hyperbolic symplectic forms. The main results are:

• If a symplectic form represents a bounded cohomology class then it is hyperbolic.

• The symplectic hyperbolicity is equivalent to a certain isoperimetric inequality.

• The fundamental group of symplectically hyperbolic manifold is non-amenable.

We also construct hyperbolic symplectic forms on certain bundles and Lefschetz fibrations, discuss the dependence of the symplectic hyperbolicity on the fundamental group and discuss some properties of the group of symplectic diffeomorphisms of a symplectically hyperbolic manifold.

Thickness‐two graphs part one: New nine‐critical graphs,permuted layer graphs,and Catlin's graphs

The purpose of this article is to offer new insight and tools toward the pursuit of the largest chromatic number in the class of thicknesstwo graphs. At present, the highest chromatic number known for a thickness‐two graph is 9, and there is only one known color‐critical such graph. We introduce 40 small 9‐critical thickness‐two graphs, and then use a newconstruction, the permuted layer graphs, together with a construction of Hajós to create an infinite family of 9‐critical thickness‐two graphs. Finally, a non‐trivial infinite subfamily of Catlin's graphs, with directly computable chromatic numbers, is shown to have thickness two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 198–214, 2008     

The fixed point property in -triples and preduals of -triples

We prove that for every member X in the class of real or complex JB^*-triples or preduals of JBW^*-triples, the following assertions are equivalent:

(1) X has the fixed point property.

(2) X has the super fixed point property.

(3) X has normal structure.

(4) X has uniform normal structure.

(5) The Banach space of X is reflexive.

As a consequence, a real or complex C^*-algebra or the predual of a real or complex W^*-algebra having the fixed point property must be finite-dimensional.

On antimagic directed graphs

An antimagic labeling of an undirected graph G with n vertices and m edges is a bijection from the set of edges of G to the integers {1, …, m} such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labeling. In (N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990, pp. 108–109), Hartsfield and Ringel conjectured that every simple connected graph, other than K₂, is antimagic. Despite considerable effort in recent years, this conjecture is still open. In this article we study a natural variation; namely, we consider antimagic labelings of directed graphs. In particular, we prove that every directed graph whose underlying undirected graph is “dense” is antimagic, and that almost every undirected d‐regular graph admits an orientation which is antimagic. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 219–232, 2010     

Application of semi-definite programming to robust stability of delay systems

We study here robust stability of linear systems with several uncertain incommensurate delays, more precisely the property usually called delay-dependent stability. The main result of this paper consists in establishing that the latter is equivalent to the feasibility of some Linear Matrix Inequality (LMI), a convex optimization problem whose numerical solution is well documented.The method is based on two main techniques:

• use of Padé approximation to transform the system into some singularly perturbed finite-dimensional system, for which robust dichotomy has to be checked;

• recursive applications of Generalized Kalman–Yakubovich–Popov (KYP) lemma to characterise by an LMI the previous property.

Book Reviews

Methods of Intermediate Problems for Eigenvalues: Theory and Ramifications, by Alexander Weinstein and William Stenger. Academic Press, 1971. ($16.00)

Combinatorics, Proceedings of the British Combinatorial Conference 1973, Edited by T.P. McDnough and V.C. Mavron, London Mathematical Society Lecture Note Series 13, Cambridge University Press, London, New York, 1974. 204pp.($9.95)     

On spaces which are linearly D

We introduce a generalization of D-spaces, which we call linearly D-spaces. The following results are obtained for a T₁-space X.

– X is linearly Lindelöf if, and only if, X is a linearly D-space of countable extent.

– X is linearly D provided that X is submetaLindelöf.

– X is linearly D provided that X is the union of finitely many linearly D-subspaces.

– X is compact provided that X is countably compact and X is the union of countably many linearly D-subspaces.

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

Supereulerian graphs and the Petersen graph

A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84(1977)]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139(1996)].     

Girth in graphs

It is shown that a graph of large girth and minimum degree at least 3 share many properties with a graph of large minimum degree. For example, it has a contraction containing a large complete graph, it contains a subgraph of large cyclic vertex-connectivity (a property which guarantees, e.g., that many prescribed independent edges are in a common cycle), it contains cycles of all even lengths modulo a prescribed natural number, and it contains many disjoint cycles of the same length. The analogous results for graphs of large minimum degree are due to Mader (Math. Ann.194 (1971), 295–312; Abh. Math. Sem. Univ. Hamburg37 (1972), 86–97), Woodall (J. Combin. Theory Ser. B22 (1977), 274–278), Bollobás (Bull. London Math. Soc.9 (1977), 97–98) and Häggkvist (Equicardinal disjoint cycles in sparse graphs, to appear). Also, a graph of large girth and minimum degree at least 3 has a cycle with many chords. An analogous result for graphs of chromatic number at least 4 has been announced by Voss (J. Combin. Theory Ser. B32 (1982), 264–285).     

Quotients of connected regular graphs of even degree

This paper introduces a method of listing all nonequivalent quotients of any connected regular graph of even degree with a given 2-factorization. The method is based on the characterization of connected 2d-regular graphs as Schreier coset graphs given by Gross (J. Combin. Theory Ser. B22 (1977), 227–232). Various representations of a given graph with a fixed 2-factorization are also investigated. The work is related to graph imbedding theory, particularly to voltage and current graphs.     

Considerations on the application of the chaos paradigm to describe the postural sway

Time-series of statokinesigram (SKG) of healthy subjects and parkinsonians are investigated and compared. This is done by employing the chaos paradigm in order to obtain the main characteristics of the SKG. The interpretation of our findings is twofold:

when a proper Theiler window is not used we find a virtual invariance of the chaos parameters when healthy subjects and parkinsonians are compared but a discrepancy of our values (correlation dimension equals to 1.4) with those found in previous works;

when a proper Theiler window is used (more) appropriately, the SKGs do not show a convergence of the fractal dimension estimates; therefore nothing can be said in terms of chaoticity of system.

Minimum degree conditions for large subgraphs

Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (such as Turán's theorem [Turán, P., On an extremal problem in graph theory (in Hungarian), Matematiko Fizicki Lapok 48 (1941), 436–452]) or on finding spanning subgraphs (such as Dirac's theorem [Dirac, G.A., Some theorems on abstract graphs, Proc. London Math. Soc. s3-2 (1952), 69–81] or more recently work of Komlós, Sárközy and Szemerédi [Komlós, J., G. N. Sárközy and E. Szemerédi, On the square of a Hamiltonian cycle in dense graphs, Random Struct. Algorithms 9 (1996), 193-211; Komlós, J., G. N. Sárközy and E. Szemerédi, Proof of the Seymour Conjecture for large graphs, Ann. Comb. 2 (1998), 43–60] towards a proof of the Pósa-Seymour conjecture). Only a few results give conditions to obtain some intermediate-sized subgraph. We contend that this neglect is unjustified. To support our contention we focus on the illustrative case of minimum degree conditions which guarantee squared-cycles of various lengths, but also offer results, conjectures and comments on other powers of paths and cycles, generalisations thereof, and hypergraph variants.     

A Generalized Chordal Metric in Control Theory Making Strong Stabilizability a Robust Property

An abstract chordal metric is defined on linear control systems described by their transfer functions. Analogous to a previous result due to Partington (Linear Operators and Linear Systems. An Analytical Approach to Control Theory. London Mathematical Society Student Texts, vol. 60, Cambridge University Press, Cambridge, 2004) for $H^\infty $ , it is shown that strong stabilizability is a robust property in this metric.