The 2-page crossing number of K_n

DOI10.1007/S00454-013-9514-0zbMATH Open1269.05078OpenAlexW43174409MaRDI QIDQ2391708FDOQ2391708

Authors: B. M. Ábrego, Silvia Fernández-Merchant, Pedro Ramos, Gelasio Salazar, 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

Recommendations

• 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
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page
• Crossing numbers of graphs

zbMATH Keywords

complete graphcrossing numbertopological 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) Graph representations (geometric and intersection representations, etc.) (05C62) Erd?s problems and related topics of discrete geometry (52C10) Specialized structures on manifolds (spin manifolds, framed manifolds, etc.) (57R15)

Cites Work

• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• The Rectilinear Crossing Number of K n : Closing in (or Are We?)
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Axioms and hulls
• Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
• A lower bound for the rectilinear crossing number
• 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
• The toroidal crossing number of the complete graph
• Title not available (Why is that?)
• On the Number of Crossings in a Complete Graph
• Special numbers of crossings for complete graphs
• The book crossing number of a graph
• Title not available (Why is that?)
• The early history of the brick factory problem
• Approximating the fixed linear crossing number
• The \(2\)-page crossing number of \(K_n\)

Cited In (23)

• On book crossing numbers of the complete graph
• Drawings of complete graphs in the projective plane
• Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
• Bounding the tripartite‐circle crossing number of complete tripartite graphs
• One- and two-page crossing numbers for some types of graphs
• Extending Drawings of Complete Graphs into Arrangements of Pseudocircles
• Title not available (Why is that?)
• From art and circuit design to geometry and combinatorics
• Bounding the tripartite-circle crossing number of complete tripartite graphs
• Topological Drawings of Complete Bipartite Graphs
• Bishellable drawings of $K_n$
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• A note on the cross-index of a complete graph based on a linear tree
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• 1-page and 2-page drawings with bounded number of crossings per edge
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• The bipartite-cylindrical crossing number of the complete bipartite graph
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill
• The crossing number of twisted graphs
• On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page
• A contribution to Guy's conjecture
• Closing in on Hill's Conjecture

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

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