Back to search

University of Waterloo

On 2-crossing-critical graphs with a V8-minor

Abstract

dc:description.abstract

The crossing number of a graph is the minimum number of pairwise edge crossings in a drawing of a graph. A graph $G$ is $k$-crossing-critical if it has crossing number at least $k$, and any subgraph of $G$ has crossing number less than $k$. A consequence of Kuratowski's theorem is that 1-critical graphs are subdivisions of K3,3 and K5. The graph V2n is a $2n$-cycle with $n$ diameters. Bokal, Oporowski, Richter and Salazar found in \cite{bigpaper} all the critical graphs except the ones that contain a V8 minor and no V10 minor. We show that a 4-connected graph $G$ has crossing number at least 2 if and only if for each pair of disjoint edges there are two disjoint cycles containing them. Using a generalization of this result we found limitations for the 2-crossing-critical graphs remaining to classify. We showed that peripherally 4-connected 2-crossing-critical graphs have at most 4001 vertices. Furthermore, most 3-connected 2-crossing-critical graphs are obtainable by small modifications of the peripherally 4-connected ones.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Arroyo Guevara, Alan Marcelo

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/8494

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Arroyo Guevara, Alan Marcelo. On 2-crossing-critical graphs with a V8-minor. University of Waterloo, 2014. http://hdl.handle.net/10012/8494