Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)

DOI10.1007/s00454-014-9644-zzbMath1307.05058arXiv1312.3679OpenAlexW2029095819MaRDI QIDQ2256586

Jan Kynčl, Martin Balko, Radoslav Fulek

Publication date: 19 February 2015

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

Full work available at URL: https://arxiv.org/abs/1312.3679

zbMATH Keywords

crossing numbercomplete graphodd crossing numbermonotone drawingmonotone odd crossing numbershellable drawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Two disjoint 5-holes in point sets ⋮ On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens ⋮ Complete graph drawings up to triangle mutations ⋮ On crossing-families in planar point sets ⋮ Edge-minimum saturated \(k\)-planar drawings ⋮ An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings ⋮ Bishellable drawings of $K_n$ ⋮ Bounding the tripartite‐circle crossing number of complete tripartite graphs ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Topological drawings meet classical theorems from convex geometry ⋮ Twisted ways to find plane structures in simple drawings of complete graphs ⋮ A Note on Universal Point Sets for Planar Graphs ⋮ A note on universal point sets for planar graphs ⋮ A SAT attack on the Erdős-Szekeres conjecture ⋮ Unnamed Item ⋮ On plane subgraphs of complete topological drawings ⋮ A SAT attack on the Erdős-Szekeres conjecture ⋮ Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\) ⋮ Unnamed Item ⋮ Induced Ramsey-type results and binary predicates for point sets ⋮ Taking a detour; or, Gioan's theorem, and pseudolinear drawings of complete graphs ⋮ A superlinear lower bound on the number of 5-holes ⋮ Closing in on Hill's Conjecture ⋮ Crossing lemma for the odd-crossing number ⋮ Topological Drawings Meet Classical Theorems from Convex Geometry ⋮ On the Maximum Number of Crossings in Star-Simple Drawings of $$K_n$$ with No Empty Lens

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• Simple realizability of complete abstract topological graphs in P
• Semispaces of configurations, cell complexes of arrangements
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Abstract order type extension and new results on the rectilinear crossing number
• Note on the pair-crossing number and the odd-crossing number
• An extended lower bound on the number of(\(\leqslant k\))-edges to generalized configurations of points and the pseudolinear crossing number of \(K_n\)
• Removing even crossings on surfaces
• An infinite family of minor-minimal nonrealizable 3-chirotopes
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• Axioms and hulls
• Special numbers of crossings for complete graphs
• The graph crossing number and its variants: a survey
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
• The 2-page crossing number of \(K_{n}\)
• Odd crossing number and crossing number are not the same
• \(k\)-sets, convex quadrilaterals, and the rectilinear crossing number of \(K_{n}\)
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• A lower bound for the rectilinear crossing number
• Hanani–Tutte, Monotone Drawings, and Level-Planarity
• Multidimensional Sorting
• Monotone Crossing Number
• A central approach to bound the number of crossings in a generalized configuration
• Computer solution to the 17-point Erdős-Szekeres problem
• Complexity of Some Geometric and Topological Problems
• Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
• Hanani-Tutte and Related Results
• The crossing number of K₁₁ is 100
• On the Number of Crossings in a Complete Graph
• Adjacent Crossings Do Matter
• Sweeps, arrangements and signotopes