tailieunhanh - Báo cáo toán học: "A Note on Obstructions to Clustered Planarity"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A Note on Obstructions to Clustered Planarity. | A Note on Obstructions to Clustered Planarity Jamie Sneddon Department of Mathematics The University of Auckland Auckland New Zealand Paul Bonnington Monash e-Research Centre Monash University Melbourne Australia Submitted Apr 12 2010 Accepted Jul 27 2011 Published Aug 5 2011 Mathematics Subject Classifications 05C10 05C20 05C83 Abstract A planar digraph D is clustered planar if in some planar embedding of D we have at each vertex the in-arcs occurring sequentially in the local rotation. By supplementing the operations used to form the usual minors in Kuratowski s theorem clustered planar digraphs are characterised. 1 Introduction Kuratowski s theorem is a well known result that characterises planar graphs. A topological minor of a graph G is formed by some combination of three operations vertex removal edge removal and smoothing. Smoothing involves replacing two edges meeting at a degree two vertex with a single edge. Under the implied ordering the minimal non-planar graphs or so-called obstructions to planarity are K3 3 and K5. Kuratowski s theorem and Robertson and Seymour s epic fundamental theorem for topological graph theory culminating in 5 do not apply to digraphs. When restrictions are placed on the nature of the digraph embedding the operations used to form digraph minors may be restricted or modified it is no longer certain that the set of obstructions under a restricted or modified partial order is finite. Bonnington et. al. 1 2 have investigated Eulerian planar digraphs that is digraphs with planar embeddings in which the in-arcs and out-arcs alternate around each vertex. Pisanski 4 has investigated the genus distribution and embeddings of graphs with clustered in-arcs at each vertex and clustered planar graphs in particular. This paper investigates extending the use of minors THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P159 1 in an altered sense for digraphs with conditions placed on the .