The Crossing Number of Seq-Shellable Drawings of Complete Graphs

DOI10.1007/978-3-319-94667-2_23arXiv1803.07515MaRDI QIDQ6299330

Publication date: 20 March 2018

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

n l e q 12

. 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.

Mathematics Subject Classification ID

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

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)