On the Maximum Number of Crossings in Star-Simple Drawings of K_n with No Empty Lens
From MaRDI portal
Publication:6347709
DOI10.1007/978-3-030-68766-3_30arXiv2008.11058MaRDI QIDQ6347709FDOQ6347709
Authors: Stefan Felsner, Kristin Knorr, Irene Parada 
Publication date: 25 August 2020
Abstract: A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. When allowing empty lenses (a face in the arrangement induced by two edges that is bounded by a 2-cycle), two independent edges may cross arbitrarily many times in a star-simple drawing. We consider star-simple drawings of with no empty lens. In this setting we prove an upper bound of on the maximum number of crossings between any pair of edges. It follows that the total number of crossings is finite and upper bounded by .
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
This page was built for publication: On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347709)
