Improved lower bounds on book crossing numbers of complete graphs

E. de Klerk, D.V. Pasechnik, G. Salazar

Research output: Contribution to journalArticleScientificpeer-review

Abstract

A "book with k pages" consists of a straight line (the "spine") and k half-planes (the "pages"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number nu_k(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs K_n. We use semidefinite programming techniques to give improved lower bounds on nu_k(K_n) for various values of k. We also use a maximum satisfiability reformulation to calculate the exact value of nu_k(K_n) for several values of k and n. Finally, we investigate the best construction known for drawing K_n in k pages, calculate the resulting number of crossings, and discuss this upper bound in the light of the new results reported in this paper.
Original languageEnglish
Pages (from-to)87-105
JournalSIAM Journal on Discrete Mathematics
Volume18
Issue number1
Publication statusPublished - 2013

Fingerprint

Crossing number
Complete Graph
Spine
Lower bound
Calculate
Semidefinite Programming
Graph in graph theory
Reformulation
Half-plane
Straight Line
Upper bound
Drawing

Cite this

de Klerk, E. ; Pasechnik, D.V. ; Salazar, G. / Improved lower bounds on book crossing numbers of complete graphs. In: SIAM Journal on Discrete Mathematics. 2013 ; Vol. 18, No. 1. pp. 87-105.
@article{bac0e9c5a8d54b78a39cd6b5a2a6d87f,
title = "Improved lower bounds on book crossing numbers of complete graphs",
abstract = "A {"}book with k pages{"} consists of a straight line (the {"}spine{"}) and k half-planes (the {"}pages{"}), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number nu_k(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs K_n. We use semidefinite programming techniques to give improved lower bounds on nu_k(K_n) for various values of k. We also use a maximum satisfiability reformulation to calculate the exact value of nu_k(K_n) for several values of k and n. Finally, we investigate the best construction known for drawing K_n in k pages, calculate the resulting number of crossings, and discuss this upper bound in the light of the new results reported in this paper.",
author = "{de Klerk}, E. and D.V. Pasechnik and G. Salazar",
year = "2013",
language = "English",
volume = "18",
pages = "87--105",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

Improved lower bounds on book crossing numbers of complete graphs. / de Klerk, E.; Pasechnik, D.V.; Salazar, G.

In: SIAM Journal on Discrete Mathematics, Vol. 18, No. 1, 2013, p. 87-105.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Improved lower bounds on book crossing numbers of complete graphs

AU - de Klerk, E.

AU - Pasechnik, D.V.

AU - Salazar, G.

PY - 2013

Y1 - 2013

N2 - A "book with k pages" consists of a straight line (the "spine") and k half-planes (the "pages"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number nu_k(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs K_n. We use semidefinite programming techniques to give improved lower bounds on nu_k(K_n) for various values of k. We also use a maximum satisfiability reformulation to calculate the exact value of nu_k(K_n) for several values of k and n. Finally, we investigate the best construction known for drawing K_n in k pages, calculate the resulting number of crossings, and discuss this upper bound in the light of the new results reported in this paper.

AB - A "book with k pages" consists of a straight line (the "spine") and k half-planes (the "pages"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number nu_k(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs K_n. We use semidefinite programming techniques to give improved lower bounds on nu_k(K_n) for various values of k. We also use a maximum satisfiability reformulation to calculate the exact value of nu_k(K_n) for several values of k and n. Finally, we investigate the best construction known for drawing K_n in k pages, calculate the resulting number of crossings, and discuss this upper bound in the light of the new results reported in this paper.

M3 - Article

VL - 18

SP - 87

EP - 105

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 1

ER -