2-crossing critical graphs with a V8 minor

graph theory;crossing number;Combinatorics and Optimization

Austin, Beth Ann

University of Waterloo

关键词: graph theory;    crossing number;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/6464/1/Austin_Elizabeth.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

The crossing number of a graph is the minimum number of pairwise crossings of edges among all planar drawings of the graph. A graph G is k-crossing critical if it has crossing number k and any proper subgraph of G has a crossing number less than k.The set of 1-crossing critical graphs is is determined by Kuratowski’s Theorem to be {K5, K3,3}. Work has been done to approach the problem of classifying all 2-crossing critical graphs. The graph V2n is a cycle on 2n vertices with n intersecting chords. The only remaining graphs to find in the classification of 2-crossing critical graphs are those that are 3-connected with a V8 minor but no V10 minor.This paper seeks to fill some of this gap by defining and completely describing a class of graphs called fully covered. In addition, we examine other ways in which graphs may be 2-crossing critical. This discussion classifies all known examples of 3-connected, 2-crossing critical graphs with a V8 minor but no V10 minor.