The 2-page crossing number of \(K_{n}\)

DOI10.1007/s00454-013-9514-0zbMath1269.05078OpenAlexW43174409MaRDI QIDQ2391708

Gelasio Salazar, Pedro A. Ramos, Bernardo M. Ábrego, Silvia Fernández-Merchant, Oswin Aichholzer

Publication date: 5 August 2013

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

Full work available at URL: https://doi.org/10.1007/s00454-013-9514-0

zbMATH Keywords

crossing numbercomplete graphtopological drawing2-page drawingbook drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Erd?s problems and related topics of discrete geometry (52C10) Specialized structures on manifolds (spin manifolds, framed manifolds, etc.) (57R15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (18)

Bishellable drawings of $K_n$ ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ The crossing number of twisted graphs ⋮ 1-page and 2-page drawings with bounded number of crossings per edge ⋮ Bounding the tripartite‐circle crossing number of complete tripartite graphs ⋮ From art and circuit design to geometry and combinatorics ⋮ Topological Drawings of Complete Bipartite Graphs ⋮ Unnamed Item ⋮ Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\) ⋮ A note on the cross-index of a complete graph based on a linear tree ⋮ Shellable drawings and the cylindrical crossing number of \(K_n\) ⋮ The bipartite-cylindrical crossing number of the complete bipartite graph ⋮ On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page ⋮ The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube ⋮ Closing in on Hill's Conjecture ⋮ Extending Drawings of Complete Graphs into Arrangements of Pseudocircles ⋮ Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill ⋮ A contribution to Guy's conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• Axioms and hulls
• Special numbers of crossings for complete graphs
• Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
• The early history of the brick factory problem
• Approximating the fixed linear crossing number
• A lower bound for the rectilinear crossing number
• The Rectilinear Crossing Number of K n : Closing in (or Are We?)
• The 2-page crossing number of K _n
• Improved Lower Bounds for the 2-Page Crossing Numbers of $K_{m,n}$ and $K_n$ via Semidefinite Programming
• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• The book crossing number of a graph
• The toroidal crossing number of the complete graph
• On the Number of Crossings in a Complete Graph

This page was built for publication: The 2-page crossing number of \(K_{n}\)