Search

We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of planar graphs. The characterization is formulated in terms of inhomogeneous wreath products. In the proof, we combine techniques from combinatorics, group theory, and geometry. Our result significantly improves the Babai's description (1975). [ABSTRACT FROM AUTHOR]

A graph G covers a graph H if there exists a locally bijective homomorphism from G to H . We deal with regular coverings in which this homomorphism is prescribed by an action of a semiregular subgroup Γ of Aut ( G ) ; so H ≅ G ∕ Γ . In this paper, we study the behavior of regular graph covering with respect to 1-cuts and2-cuts in G . We describe reductions which produce a series of graphs G = G 0 , … , G r such that G i + 1 is created from G i by replacing certain inclusion minimal subgraphs with colored edges. The process ends with a primitive graph G r which is either 3-connected, or a cycle, or K 2 . This reduction can be viewed as a non-trivial modification of reductions of Mac Lane (1937), Trachtenbrot (1958), Tutte (1966), Hopcroft and Tarjan (1973), Cuningham and Edmonds (1980), Walsh (1982), and others. A novel feature of our approach is that in each step all essential information about symmetries of G are preserved. A regular covering projection G 0 → H 0 induces regular covering projections G i → H i where H i is the i th quotient reduction of H 0 . This property allows to construct all possible quotients H 0 of G 0 from the possible quotients H r of G r . By applying this method to planar graphs, we give a proof of Negami’s Theorem (1988). Our structural results are also used in subsequent papers for regular covering testing when G is a planar graph and for an inductive characterization of the automorphism groups of planar graphs (see Babai (1973) as well). [ABSTRACT FROM AUTHOR]

Abstract: A conjecture of de Caen and Székely [D. de Caen, L.A. Székely, J. Combin. Theory Ser. A 77 (1997) 268–278] asserts that every arrangement of n points and m lines in the plane contains at most triangles with vertices in the points and sides on the lines of the arrangement. We disprove the conjecture by constructing an arrangement of n points and n lines with such triangles. [ABSTRACT FROM AUTHOR]

The cop number of a graph G is the smallest k such that k cops win the game of cops and robber on G . We investigate the maximum cop number of geometric intersection graphs, which are graphs whose vertices are represented by geometric shapes and edges by their intersections. We establish the following dichotomy for previously studied classes of intersection graphs: • The intersection graphs of arc-connected sets in the plane (called string graphs ) have cop number at most 15, and more generally, the intersection graphs of arc-connected subsets of a surface have cop number at most 10 g + 15 in case of orientable surface of genus g , and at most 10 g ′ + 15 in case of non-orientable surface of Euler genus g ′ . For more restricted classes of intersection graphs, we obtain better bounds: the maximum cop number of interval filament graphs is two, and the maximum cop number of outer-string graphs is between 3 and 4. • The intersection graphs of disconnected 2-dimensional sets or of 3-dimensional sets have unbounded cop number even in very restricted settings. For instance, it follows from known results that the cop number is unbounded on intersection graphs of two-element subsets of a line. We further show that it is also unbounded on intersection graphs of 3-dimensional unit balls, of 3-dimensional unit cubes or of 3-dimensional axis-aligned unit segments. [ABSTRACT FROM AUTHOR]