Ponencia
Monotone crossing number of complete graphs
Autor/es | Balko, Martin
Fulek, Radoslav Kynčl, Jan |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-06-07 |
Publicado en |
|
Resumen | 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. |
Identificador del proyecto | GACR GIG/11/E023
SVV-2013-267313 |
Cita | Balko, M., Fulek, R. y Kynčl, J. (2013). Monotone crossing number of complete graphs. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Monotone crossing number of ... | 795.9Kb | [PDF] | Ver/ | |