Crossing-number critical graphs have bounded path-width

DOI10.1016/S0095-8956(03)00037-6MaRDI QIDQ1400969zbMATH OpenWikidataFDO

Authors Petr Hliněný

Publication date 17 August 2003

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0095-8956(03)00037-6

zbMATH Keywords

crossing numbercrossing-critical graphgraph embeddingpath-width

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

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)].

Recommendations

• scientific article; zbMATH DE number 2084270
• Stars and Bonds in Crossing-Critical Graphs
• Crossing-critical graphs with large maximum degree
• Stars and bonds in crossing-critical graphs
• Crossing-critical edges and Kuratowski subgraphs of a graph

Cites work

• A framework for solving VLSI graph layout problems
• Construction of crossing-critical graphs
• Crossing Number is NP-Complete
• Crossing-Free Subgraphs
• Embedding grids in surfaces
• Graph minors. I. Excluding a forest
• Graphs drawn with few crossings per edge
• scientific article; zbMATH DE number 2084270 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 1156593 (Why is no real title available?)
• scientific article; zbMATH DE number 1156616 (Why is no real title available?)
• Intersections of curve systems and the crossing number of \(C_ 5\times C_ 5\)
• Large non-planar graphs and an application to crossing-critical graphs
• Minimal graphs with crossing number at least \(k\)
• Quickly excluding a forest
• Toward a theory of crossing numbers

Cited in

(23)

• On degree properties of crossing-critical families of graphs
• Embedding grids in surfaces
• Crossing number for graphs with bounded pathwidth
• Improvement on the crossing number of crossing-critical graphs
• On the crossing numbers of loop networks and generalized Petersen graphs
• Characterizing 2-crossing-critical graphs
• New upper bounds for the crossing numbers of crossing-critical graphs
• Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\)
• scientific article; zbMATH DE number 2084270 (Why is no real title available?)
• Stars and bonds in crossing-critical graphs
• Nearly light cycles in embedded graphs and crossing-critical graphs
• ON THE ADDITIVITY OF CROSSING NUMBERS OF GRAPHS
• Properties of large 2-crossing-critical graphs
• Bounded degree conjecture holds precisely for c-crossing-critical graphs with c 12
• Structure and generation of crossing-critical graphs
• scientific article; zbMATH DE number 7278018 (Why is no real title available?)
• Stars and Bonds in Crossing-Critical Graphs
• Domination and independence number of large 2-crossing-critical graphs
• 2-Layer Graph Drawings with Bounded Pathwidth
• On 13-crossing-critical graphs with arbitrarily large degrees
• Nested cycles in large triangulations and crossing-critical graphs
• Crossing-critical edges and Kuratowski subgraphs of a graph
• Crossing-critical graphs with large maximum degree

This page was built for publication: Crossing-number critical graphs have bounded path-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1400969)