Crossing-number critical graphs have bounded path-width (Q1400969): Difference between revisions

The crossing number of a graph \(G\), denoted by \(\text{cr}(G)\), is defined as the smallest possible number of edge-crossings in a drawing of \(G\) in the plane. A graph \(G\) is crossing-critical if \(\text{cr}(G-e)<\text{cr}(G)\) for all edges \(e\) of \(G\). The author proves that a crossing-critical graph cannot contain a subdivision of a ``large'' binary tree. This assertion was conjectured earlier by Salazar; see \textit{J. Geelen, B. Richter} and \textit{G. Salazar} [Embedding grids on surfaces (manuscript, 2000)].