Book crossing numbers of the complete graph and small local convex crossing numbers
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2016
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910449909366784 |
|---|---|
| author | Ábrego, Bernardo M. Dandurand, Julia Fernández-Merchant, Silvia Lagoda, Evgeniya Sapozhnikov, Yakov |
| author_facet | Ábrego, Bernardo M. Dandurand, Julia Fernández-Merchant, Silvia Lagoda, Evgeniya Sapozhnikov, Yakov |
| contents | A $ k $-page book drawing of a graph $ G $ is a drawing of $ G $ on $ k $ halfplanes with common boundary $ l $, a line, where the vertices are on $ l $ and the edges cannot cross $ l $. The $ k $-page book crossing number of the graph $ G $, denoted by $ ν_k(G) $, is the minimum number of edge-crossings over all $ k $-page book drawings of $ G $. Let $G=K_n$ be the complete graph on $n$ vertices. We improve the lower bounds on $ ν_k(K_n) $ for all $ k\geq 14 $ and determine $ ν_k(K_n) $ whenever $ 2 < n/k \leq 3 $. Our proofs rely on bounding the number of edges in convex graphs with small local crossing numbers. In particular, we determine the maximum number of edges that a convex graph with local crossing number at most $ \ell $ can have for $ \ell\leq 4 $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1607_00131 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Book crossing numbers of the complete graph and small local convex crossing numbers Ábrego, Bernardo M. Dandurand, Julia Fernández-Merchant, Silvia Lagoda, Evgeniya Sapozhnikov, Yakov Combinatorics 05C10, 05C62, 52C10, 68R10 A $ k $-page book drawing of a graph $ G $ is a drawing of $ G $ on $ k $ halfplanes with common boundary $ l $, a line, where the vertices are on $ l $ and the edges cannot cross $ l $. The $ k $-page book crossing number of the graph $ G $, denoted by $ ν_k(G) $, is the minimum number of edge-crossings over all $ k $-page book drawings of $ G $. Let $G=K_n$ be the complete graph on $n$ vertices. We improve the lower bounds on $ ν_k(K_n) $ for all $ k\geq 14 $ and determine $ ν_k(K_n) $ whenever $ 2 < n/k \leq 3 $. Our proofs rely on bounding the number of edges in convex graphs with small local crossing numbers. In particular, we determine the maximum number of edges that a convex graph with local crossing number at most $ \ell $ can have for $ \ell\leq 4 $. |
| title | Book crossing numbers of the complete graph and small local convex crossing numbers |
| topic | Combinatorics 05C10, 05C62, 52C10, 68R10 |
| url | https://arxiv.org/abs/1607.00131 |