Bishellable drawings of K_n

DOI10.1137/17M1147974MaRDI QIDQ4555043zbMATH OpenOpenAlexFDO

Authors Oswin Aichholzer, Silvia Fernández-Merchant, Bojan Mohar, Petra Mutzel, Pedro Ramos, Birgit Vogtenhuber, B. M. Ábrego, Daniel McQuillan, R. B. Richter

Publication date 19 November 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bishellabilitycomplete graphcrossing numbergood drawingshellabilitysimple drawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph $K_n$ is $H(n)=frac14leftlfloorfracmathstrutnmathstrut2ightfloorleftlfloorfracmathstrutn-1mathstrut2ightfloorleftlfloorfracmathstrutn-2mathstrut2ightfloorleftlfloorfracmathstrutn-3mathstrut2ightfloor$. 'Abrego et al. introduced the notion of shellability of a drawing $D$ of $K_n$. They proved that if $D$ is $s$-shellable for some $sgeqlfloorfracn2floor$, then $D$ has at least $H(n)$ crossings. This is the first combinatorial condition on a drawing that guarantees at least $H(n)$ crossings. In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $bleqs-2$, also $b$-bishellable. Our main result is that $(lfloorfracn2floor!-!2)$-bishellability of a drawing $D$ of $K_n$ also guarantees, with a simpler proof than for $s$-shellability, that $D$ has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $sgeq5$. This shows that we have properly extended the class of drawings for which the Harary-Hill Conjecture is proved. Moreover, we provide an infinite family of drawings of $K_n$ that are $(lfloorfracn2floor!-!2)$-bishellable, but not $s$-shellable for any $sgeqlfloorfracn2floor$.

Recommendations

• Shellable drawings and the cylindrical crossing number of \(K_n\)
• Geometric drawings of \(K_{n}\) with few crossings
• scientific article; zbMATH DE number 7030516
• Topological Drawings of Complete Bipartite Graphs
• k-shellable simplicial complexes and graphs
• The crossing number of seq-shellable drawings of complete graphs
• Bipartite graphs, upward drawings, and planarity
• Drawing \(K_{2,n}\): A lower bound
• Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
• Biclique Edge Cover Graphs and Confluent Drawings

Cites work

• A lower bound for the rectilinear crossing number
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• scientific article; zbMATH DE number 2145237 (Why is no real title available?)
• scientific article; zbMATH DE number 3258070 (Why is no real title available?)
• scientific article; zbMATH DE number 3394160 (Why is no real title available?)
• New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\)
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• On the crossing number of K_n without computer assistance
• On the Number of Crossings in a Complete Graph
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• The 2-page crossing number of \(K_{n}\)
• The crossing number of K₁₁ is 100
• The early history of the brick factory problem

Cited in

(8)

• The crossing number of seq-shellable drawings of complete graphs
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• Extending drawings of complete graphs into arrangements of pseudocircles
• On plane subgraphs of complete topological drawings
• Bounding the tripartite‐circle crossing number of complete tripartite graphs
• Towards crossing-free Hamiltonian cycles in simple drawings of complete graphs
• Levels in arrangements: linear relations, the g-matrix, and applications to crossing numbers

This page was built for publication: Bishellable drawings of $K_n$

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