An improved upper bound on the crossing number of the hypercube

DOI10.1002/JGT.20330MaRDI QIDQ3605145zbMATH OpenOpenAlexFDO

Authors Celina Miraglia Herrera de Figueiredo, Ondrej Sýkora, Imrich Vrt'o, Luerbio Faria

Publication date 20 February 2009

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.20330

zbMATH Keywords

\(n\)-cubecrossing numbertopological graph theory

Mathematics Subject Classification ID

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

Recommendations

• An improved upper bound on the crossing number of the hypercube.
• Bounds for the crossing number of the N‐cube
• Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes
• The maximum rectilinear crossing number of the \(n\) dimensional cube graph
• On Eggleton and Guy's conjectured upper bound for the crossing number of the \(n\)-cube

Cites work

• scientific article; zbMATH DE number 1054768 (Why is no real title available?)
• scientific article; zbMATH DE number 3344600 (Why is no real title available?)
• Bounds for the crossing number of the N‐cube
• Crossing Number is NP-Complete
• On Eggleton and Guy's conjectured upper bound for the crossing number of the \(n\)-cube
• Planarizing graphs---a survey and annotated bibliography

Cited in

(23)

• scientific article; zbMATH DE number 219248 (Why is no real title available?)
• Bounds for the crossing number of the N‐cube
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• scientific article; zbMATH DE number 1741018 (Why is no real title available?)
• Improved bounds on the crossing number of butterfly network
• On Eggleton and Guy's conjectured upper bound for the crossing number of the \(n\)-cube
• The crossing number of folded hypercubes
• An improved upper bound on the crossing number of the hypercube.
• Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation
• On crossing numbers of hypercubes and cube connected cycles
• The maximum rectilinear crossing number of the \(n\) dimensional cube graph
• A survey of graphs with known or bounded crossing numbers
• Improved upper bounds on the crossing number
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• New bounds on the biplanar crossing number of low-dimensional hypercubes: how low can you go?
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• Drawing a graph in a hypercube
• Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes
• Upper bound for the crossing number of \(Q_n \times K_3\)
• A new upper bound on the queuenumber of hypercubes
• The crossing number of locally twisted cubes \(L T Q_n\)
• On the central levels problem
• An upper bound for the crossing number of augmented cubes

This page was built for publication: An improved upper bound on the crossing number of the hypercube

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