Odd crossing number and crossing number are not the same

DOI10.1007/S00454-008-9058-XMaRDI QIDQ2482214zbMATH OpenOpenAlexWikidataFDO

Authors Michael J. Pelsmajer, Marcus Schaefer, D. Štefankovič

Publication date 16 April 2008

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-008-9058-x

zbMATH Keywords

crossing number

Mathematics Subject Classification ID

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

Review text

The crossing number \(\text{cr}(G)\) of a graph \(G\) is the minimum number of edge crossings, taken over all drawing of \(G\) in the plane. Similarly \(\text{per}(G)\) (respectively \(\text{ocr}(G)\)) denotes the minimum number of pairs of edges which cross at least once (respectively an odd number of times), over all drawings of \(G\) in the plane. It is immediate that \(\text{ocr}(G)\leq\text{pcr}(G)\leq\text{cr}(G)\). \textit{J. Pach} and \textit{G. Tóth} [J. Comb. Theory, Ser. B 80, No. 2, 225--246 (2000; Zbl 1023.05042)] asked if the inequalities are actually equalities. The present authors construct a simple example of a graph (and then an infinite family of simple graphs) for which \(\text{ocr}(G)< \text{pcr}(G)\).

Recommendations

• Graph Drawing
• Note on the pair-crossing number and the odd-crossing number
• Adjacent Crossings Do Matter
• Adjacent crossings do matter
• A better bound for the pair-crossing number

Cites work

• A successful concept for measuring non-planarity of graphs: The crossing number.
• Crossing Number is NP-Complete
• Crossing number, pair-crossing number, and expansion
• scientific article; zbMATH DE number 5763167 (Why is no real title available?)
• scientific article; zbMATH DE number 1454642 (Why is no real title available?)
• scientific article; zbMATH DE number 1507304 (Why is no real title available?)
• scientific article; zbMATH DE number 5019924 (Why is no real title available?)
• Topological graph theory.
• Toward a theory of crossing numbers
• Which crossing number is it anyway?
• Über wesentlich unplättbare Kurven im dreidimensionalen Raume

Cited in

(21)

• On the degenerate crossing number
• Crossing lemma for the odd-crossing number
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• The bipartite-cylindrical crossing number of the complete bipartite graph
• On the Pseudolinear Crossing Number
• Hanani-Tutte and monotone drawings
• Monotone Crossing Number
• Removing independently even crossings
• The Orchard crossing number of an abstract graph
• The Crossing Number of Graphs: Theory and Computation
• scientific article; zbMATH DE number 5019924 (Why is no real title available?)
• Crossing numbers of graphs with rotation systems
• Adjacent crossings do matter
• Adjacent Crossings Do Matter
• Graph Drawing
• Bounding the tripartite‐circle crossing number of complete tripartite graphs
• Bounding the tripartite-circle crossing number of complete tripartite graphs
• Note on min-k-planar drawings of graphs
• Strong Hanani-Tutte for the torus
• A unified FPT framework for crossing number problems
• Note on the pair-crossing number and the odd-crossing number

This page was built for publication: Odd crossing number and crossing number are not the same

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