Book drawings of complete bipartite graphs
From MaRDI portal
Publication:2440102
DOI10.1016/J.DAM.2013.11.001zbMATH Open1284.05178arXiv1210.2918OpenAlexW2032747526WikidataQ56689189 ScholiaQ56689189MaRDI QIDQ2440102FDOQ2440102
E. de Klerk, Gelasio Salazar, Dmitrii V. Pasechnik
Publication date: 27 March 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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 pagenumber of a graph G is the minimum k such that G admits a k-page embedding (that is, a k-page drawing with no edge crossings). The k-page crossing number nu_k(G) of G is the minimum number of crossings in a k-page drawing of G. We investigate the pagenumbers and k-page crossing numbers of complete bipartite graphs. We find the exact pagenumbers of several complete bipartite graphs, and use these pagenumbers to find the exact k-page crossing number of K_{k+1,n} for 3<=k<=6. We also prove the general asymptotic estimate lim_{k->oo} lim_{n->oo} nu_k(K_{k+1,n})/(2n^2/k^2)=1. Finally, we give general upper bounds for nu_k(K_{m,n}), and relate these bounds to the k-planar crossing numbers of K_{m,n} and K_n.
Full work available at URL: https://arxiv.org/abs/1210.2918
Recommendations
- Improved lower bounds on book crossing numbers of complete graphs
- On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page
- On the pagenumber of complete bipartite graphs
- On the page number of complete odd-partite graphs
- Pagenumber of complete bipartite graphs
Cites Work
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- On the Shannon capacity of a graph
- Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
- The book thickness of a graph
- Embedding planar graphs in four pages
- On the pagenumber of complete bipartite graphs
- Title not available (Why is that?)
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- Pagenumber of complete bipartite graphs
- Cyclic‐order graphs and Zarankiewicz's crossing‐number conjecture
- Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs
- The crossing number of K5,n
- On a problem of P. Turan concerning graphs
- Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
- Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
- Solving hard mixed-integer programming problems with Xpress-MP: a MIPLIB 2003 case study
- Title not available (Why is that?)
- The book crossing number of a graph
- Biplanar crossing numbers. I: A survey of results and problems
- On \(k\)-planar crossing numbers
- Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method
- Improved lower bounds on book crossing numbers of complete graphs
- Title not available (Why is that?)
Cited In (7)
- On Crossing Sets, Disjoint Sets, and Pagenumber
- Topological Drawings of Complete Bipartite Graphs
- Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
- Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill
- Mutual witness Gabriel drawings of complete bipartite graphs
- Title not available (Why is that?)
- Book Embeddings of Regular Graphs
Uses Software
This page was built for publication: Book drawings of complete bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2440102)
