The Crossing Number of Seq-Shellable Drawings of Complete Graphs

DOI10.1007/978-3-319-94667-2_23MaRDI QIDQ6299330arXivFDO

Authors Petra Mutzel, Lutz Oettershagen

Publication date 20 March 2018

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-319-94667-2_23

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CGmath.CO

Abstract: The Harary-Hill conjecture states that for every $n>0$ the complete graph on $n$ vertices $K_n$, the minimum number of crossings over all its possible drawings equals �egin{align*} H(n) := frac{1}{4}Biglfloorfrac{n}{2}Big floorBiglfloorfrac{n-1}{2}Big floorBiglfloorfrac{n-2}{2}Big floorBiglfloorfrac{n-3}{2}Big floor ext{.} end{align*} So far, the lower bound of the conjecture could only be verified for arbitrary drawings of $K_n$ with $nleq12$. In recent years, progress has been made in verifying the conjecture for certain classes of drawings, for example $2$-page-book, $x$-monotone, $x$-bounded, shellable and bishellable drawings. Up to now, the class of bishellable drawings was the broadest class for which the Harary-Hill conjecture has been verified, as it contains all beforehand mentioned classes. In this work, we introduce the class of seq-shellable drawings and verify the Harary-Hill conjecture for this new class. We show that bishellability implies seq-shellability and exhibit a non-bishellable but seq-shellable drawing of $K_{11}$, therefore the class of seq-shellable drawings strictly contains the class of bishellable drawings.

This page was built for publication: The Crossing Number of Seq-Shellable Drawings of Complete Graphs

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