Opened Access Monotone crossing number of complete graphs
Estadísticas
Icon
Exportar a
Autor: 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
Fecha: 2013
Publicado en: XV Spanish Meeting on Computational Geometry (2013), p 135-138
Tipo de documento: Ponencia
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 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.
Tamaño: 795.9Kb
Formato: PDF

URI: http://hdl.handle.net/11441/61090

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones