Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method

DOI10.1002/rsa.20221zbMath1182.05040OpenAlexW3083226444MaRDI QIDQ3608305

Éva Czabarka, Ondrej Sýkora, László A. Székely, Imrich Vrt'o

Publication date: 4 March 2009

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20221

zbMATH Keywords

thicknesscrossing numbergraph drawingbiplanar crossing number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (6)

A short proof of the non-biplanarity of \(K_9\) ⋮ A short proof of the non-biplanarity of $K_9$ ⋮ Note on \(k\)-planar crossing numbers ⋮ On the 2-colored crossing number ⋮ Book drawings of complete bipartite graphs ⋮ On the \(k\)-planar local crossing number

Cites Work

• A note on Halton's conjecture
• On the thickness and arboricity of a graph
• On the thickness of graphs of given degree
• The thickness of graphs: A survey
• Biplanar graphs: A survey
• A successful concept for measuring non-planarity of graphs: The crossing number.
• Planarizing Graphs - A Survey and Annotated Bibliography
• Crossing-Free Subgraphs
• Determining the thickness of graphs is NP-hard
• Genus g Graphs Have Pagenumber O(√g)
• On VLSI layouts of the star graph and related networks

This page was built for publication: Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method