The 2-page crossing number of K_n

DOI10.1007/S00454-013-9514-0MaRDI QIDQ2391708zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

2-page drawingbook drawingcomplete graphcrossing numbertopological drawing

Mathematics Subject Classification ID

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) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• 3-symmetric and 3-decomposable geometric drawings of \(K_n\)
• A lower bound for the rectilinear crossing number
• Approximating the fixed linear crossing number
• Axioms and hulls
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• scientific article; zbMATH DE number 2145237 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 3258070 (Why is no real title available?)
• scientific article; zbMATH DE number 969978 (Why is no real title available?)
• Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• On the Number of Crossings in a Complete Graph
• Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\)
• Reduction of symmetric semidefinite programs using the regular -representation
• Special numbers of crossings for complete graphs
• The 2-page crossing number of K_n
• The book crossing number of a graph
• The early history of the brick factory problem
• The rectilinear crossing number of K_n: closing in (or are we?)
• The toroidal crossing number of the complete graph

Cited in

(29)

• The crossing number of seq-shellable drawings of complete graphs
• 1-page and 2-page drawings with bounded number of crossings per edge
• Bounding the number of non-duplicates of the \(q\)-side in simple drawings of \(K_{p,q}\)
• A contribution to Guy's conjecture
• The crossing number of twisted graphs
• Crossing numbers and combinatorial characterization of monotone drawings 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
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• 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
• 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
• Extending drawings of complete graphs into arrangements of pseudocircles
• The 2-page crossing number of \(C (3k, k)\)
• Closing in on Hill's conjecture
• Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill
• One- and two-page crossing numbers for some types of graphs
• Bounding the tripartite‐circle crossing number of complete tripartite graphs
• From art and circuit design to geometry and combinatorics
• Drawings of complete graphs in the projective plane
• Towards crossing-free Hamiltonian cycles in simple drawings of complete graphs
• On book crossing numbers of the complete graph
• Bounding the tripartite-circle crossing number of complete tripartite graphs
• A tight subexponential-time algorithm for two-page book embedding
• Levels in arrangements: linear relations, the g-matrix, and applications to crossing numbers

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)