Crossing-number critical graphs have bounded path-width
type: Item
instance of: scholarly article
title: Crossing-number critical graphs have bounded path-width
zbMATH Open document ID: 1021.05028
DOI: 10.1016/S0095-8956(03)00037-6
author: Petr Hliněný
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-17T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1965039
zbMATH Keywords: graph embedding
zbMATH Keywords: crossing number
zbMATH Keywords: crossing-critical graph
zbMATH Keywords: path-width
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
cites work: Crossing-Free Subgraphs
cites work: Q4390620
cites work: Q4390646
cites work: Quickly excluding a forest
cites work: A framework for solving VLSI graph layout problems
cites work: Q3154375
cites work: Large non-planar graphs and an application to crossing-critical graphs
cites work: Crossing Number is NP-Complete
cites work: Embedding grids in surfaces
cites work: Q3043709
cites work: Construction of crossing-critical graphs
cites work: Graphs drawn with few crossings per edge
cites work: Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)
cites work: Minimal graphs with crossing number at least \(k\)
cites work: Graph minors. I. Excluding a forest
cites work: Toward a theory of crossing numbers
Wikidata QID: Q29011978
description: scientific article; zbMATH DE number 1965039