Presentation
Monotone crossing number of complete graphs
Author/s | Balko, Martin
Fulek, Radoslav Kynčl, Jan |
Editor | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Publication Date | 2013 |
Deposit Date | 2017-06-07 |
Published in |
|
Abstract | In 1958, Hill conjectured that the minimum number of crossings in a drawing of Kn is exactly Z(n) = 1/4 n-1/2/2 n−2/2 n−3/2. Generalizing the result by
Ábrego et al. for 2-page book drawings, we prove this conjecture for ... In 1958, Hill conjectured that the minimum number of crossings in a drawing of Kn is exactly Z(n) = 1/4 n-1/2/2 n−2/2 n−3/2. Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by x-monotone curves. In fact, our proof shows that the conjecture remains true for xmonotone drawings in which adjacent edges do not cross and we count only pairs of edges which cross odd number of times. We also discuss a combinatorial characterization of these drawings. |
Project ID. | GACR GIG/11/E023
SVV-2013-267313 |
Citation | Balko, M., Fulek, R. y Kynčl, J. (2013). Monotone crossing number of complete graphs. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Monotone crossing number of ... | 795.9Kb | [PDF] | View/ | |