Notes on a theorem of Naji

We present a new proof of an algebraic characterization of circle graphs due to W. Naji.For bipartite graphs, Naji’s theorem is equivalent to an algebraic characterization of planar matroids due to J. Geelen and B. Gerards. Naji’s theorem also yields an algebraic characterization of permutation graphs.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

Wagner's theorem for Torus graphs

Wagner's theorem (any two maximal plane graphs having p vertices are equivalent under diagonal transformations) is extended to maximal torus graphs, graphs embedded in the torus with a maximal set of edges present. Thus any maximal torus graph having p vertices may be diagonally transformed into any other maximal torus graph having p vertices. As with Wagner's theorem, a normal form representing an intermediate stage in the above transformation is displayed. This result, along with Wagner's theorem, may make possible constructive characterizations of planar and toroidal graphs, through a wholly combinatorial definition of diagonal transformation.     

Graphs and their associated inverse semigroups

Directed graphs have long been used to gain an understanding of the structure of semigroups, and recently the structure of directed graph semigroups has been investigated resulting in a characterization theorem and an analog of Frucht’s Theorem. We investigate two inverse semigroups defined over undirected graphs constructed from the notions of subgraph and vertex set induced subgraph. We characterize the structure of the semilattice of idempotents and lattice of ideals of these inverse semigroups. We prove a characterization theorem that states that every graph has a unique associated inverse semigroup up to isomorphism allowing for an algebraic restatement of the Edge Reconstruction Conjecture.     

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.     

Colorful subgraphs in Kneser-like graphs

Combining Ky Fan’s theorem with ideas of Greene and Matoušek we prove a generalization of Dol’nikov’s theorem. Using another variant of the Borsuk–Ulam theorem due to Tucker and Bacon, we also prove the presence of all possible completely multicolored t-vertex complete bipartite graphs in t-colored t-chromatic Kneser graphs and in several of their relatives. In particular, this implies a generalization of a recent result of G. Spencer and F.E. Su.     

A Möbius-Invariant Power Diagram and Its Applications to Soap Bubbles and Planar Lombardi Drawing

We use three-dimensional hyperbolic geometry to define a form of power diagram for systems of circles in the plane that is invariant under Möbius transformations. By applying this construction to circle packings derived from the Koebe–Andreev–Thurston circle packing theorem, we show that every planar graph of maximum degree three has a planar Lombardi drawing (a drawing in which the edges are drawn as circular arcs, meeting at equal angles at each vertex). We use circle packing to construct planar Lombardi drawings of a special class of 4-regular planar graphs, the medial graphs of polyhedral graphs, and we show that not every 4-regular planar graph has a planar Lombardi drawing. We also use these power diagrams to characterize the graphs formed by two-dimensional soap bubble clusters (in equilibrium configurations) as being exactly the 3-regular bridgeless planar multigraphs, and we show that soap bubble clusters in stable equilibria must in addition be 3-connected.     

A note on kernels and Sperner’s Lemma

The kernel-solvability of perfect graphs was first proved by Boros and Gurvich, and later Aharoni and Holzman gave a shorter proof. Both proofs were based on Scarf’s Lemma. In this note we show that a very simple proof can be given using a polyhedral version of Sperner’s Lemma. In addition, we extend the Boros–Gurvich theorem to h-perfect graphs and to a more general setting.     

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.     

Operators associated with the Jacobi semigroup

The aim of this paper is to introduce some operators induced by the Jacobi differential operator and associated with the Jacobi semigroup, where the Jacobi measure is considered in the multidimensional case.In this context, we introduce potential operators, fractional integrals, fractional derivates, Bessel potentials and give a version of Carleson measures.We establish a version of Meyer’s multiplier theorem and by means of this theorem, we study fractional integrals and fractional derivates.Potential spaces related to Jacobi expansions are introduced and using fractional derivates, we give a characterization of these spaces. A version of Calderon’s Reproduction Formula and a version of Fefferman’s theorem are given.Finally, we present a definition of Triebel–Lizorkin spaces and Besov spaces in the Jacobi setting.     

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.     

Even signings,signed switching classes,and (−1, 1)-matrices

In this paper, algebraic and combinatorial techniques are used to establish results concerning even signings of graphs, switching classes of signed graphs, and (?1, 1)-matrices. These results primarily deal with enumeration of isomorphism types, and determining whether there are fixed elements under the action of automorphisms. A formula is given for the number of isomorphism types of even signings of any fixed simple graph. This is shown to be equal to the number of isomorphism types of switching classes of signings of the graph. A necessary and sufficient criterion is found for all switching classes fixed by a given graph automorphism to contain signings fixed by that automorphism. It is determined whether this criterion is met for all automorphisms of various graphs, including complete graphs, which yields a known result of Mallows and Sloane. As an application, a formula is developed for the number of H-equivalence classes of (?1, 1)-matrices of fixed size. Independently, using Molien's theorem and following a suggestion of Cameron's, generating series for these numbers are given. As a final application, a necessary and sufficient condition that a square (?1, 1)-matrix be switching equivalent to a symmetric matrix is given.     

A full characterization of invariant embeddability of unimodular planar graphs

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using the fact that such graphs automatically have locally finite (simply connected) drawings into the plane. For the case of graphs with multiple ends the question was left open. We revisit Halin's graph theoretic characterization of graphs that have a locally finite embedding into the plane. Then we prove that such unimodular random graphs do have a locally finite invariant embedding into the Euclidean or the hyperbolic plane, depending on whether the graph is amenable or not.     

Note on 3-choosability of planar graphs with maximum degree 4

Deciding whether a planar graph (even of maximum degree 4) is 3-colorable is NP-complete. Determining subclasses of planar graphs being 3-colorable has a long history, but since Grötzsch’s result that triangle-free planar graphs are such, most of the effort was focused to solving Havel’s and Steinberg’s conjectures. In this paper, we prove that every planar graph obtained as a subgraph of the medial graph of any bipartite plane graph is 3-choosable. These graphs are allowed to have close triangles (even incident), and have no short cycles forbidden, hence representing an entirely different class than the graphs inferred by the above mentioned conjectures.     

An improvement on Marotto’s theorem and its applications to chaotification of switching systems

The controversy surrounding the correctness of Marotto’s theorem continues over the last two decades, with many researchers claiming to have found an error in the proof. In this paper, we show that Marotto’s theorem is indeed correct for analyzing the existence of chaos in the sense of Li-Yorke even after relaxing certain assumptions in the proof. In addition, we extend the theory to derive the conditions for the existence of chaos in the sense of Devaney. We show that these results can be applied to study the chaotification of linear switching systems.     

Recognizing Planar Strict Quasi-Parity Graphs

 A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with no odd chordless path between them (an “even pair”). We present an O(n ³) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9]. Received: September 21, 1998 Final version received: May 9, 2000     

A characterization of planar partial cubes

Partial cubes as well as planar graphs have been extensively investigated. In this note we introduce an additional topological kind of condition to the Chepoi’s expansion procedure that characterizes planar partial cubes. As a consequence we obtain a characterization of some other planar subclasses of partial cubes.     

Concept of a vertex in a matroid and 3-connected graphs

The concept of a matroid vertex is introduced. The vertices of a matroid of a 3-connected graph are in one-to-one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3-connected graphs implies isomorphism. The concept of a vertex of a matroid leads to an equally simple proof of Whitney's theorem on the unique embedding of a 3-connected planar graph in the sphere. It also leads to a number of new facts about 3-connected graphs. Thus, consideration of a vertex in a matroid that is the dual of the matroid of a graph leads to a natural concept of a nonseparating cycle of a graph. Whitney's theorem on cyclic isomorphism can be strengthened (even if the nonseparating cycles of a graph are considered, the theorem is found to work) and a new criterion for planarity of 3-connected graphs is obtained (in terms of nonseparating cycles).     

An arithmetic proof of John’s ellipsoid theorem

Using an idea of Voronoi in the geometric theory of positive definite quadratic forms, we give a transparent proof of John’s characterization of the unique ellipsoid of maximum volume contained in a convex body. The same idea applies to the ‘hard part’ of a generalization of John’s theorem and shows the difficulties of the corresponding ‘easy part’.Received: 8 October 2004     

On the representability of neatly embeddable CA’s by cylindric relativized algebras

Neat embedding theorems yield an abstract algebraic characterization for the representability of a given class of algebras by set algebras. Resek and Thompson’s theorem called attention to a new kind of representation in the theory of cylindric algebras, to the representation by cylindric relativised set algebras. In this paper, we present the algebraic characterization of this kind of representation; we formulate neat embedding theorems for this representation.