A new lower bound for the bipartite crossing number with applications
type: Item
instance of: scholarly article
title: A new lower bound for the bipartite crossing number with applications
zbMATH Open document ID: 0946.68102
DOI: 10.1016/S0304-3975(99)00285-6
author: Farhad Shahrokhi
author: Ondrej Sýkora
author: László A. Székely
author: Imrich Vrt'o
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
review text: Let \(G\) be a connected bipartite graph. We give a short proof, using a variation of Menger's theorem, for a new lower bound which relates the bipartite crossing number of \(G\), denoted by bcr(\(G\)), to the edge connectivity properties of \(G\). The general lower bound implies a weaker version of a very recent result, establishing a bisection-based lower bound on bcr(\(G\)) which has algorithmic consequences. Moreover, we show further applications of our general method to estimate bcr(\(G\)) for ``well structured'' families of graphs, for which tight isoperimetric inequalities are available. For hypercubes and two-dimensional meshes, the upper bounds (asymptotically) are within multiplicative factors of 4 and 2, from the lower bounds, respectively. The general lower bound also implies a lower bound involving eigenvalues of \(G\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W35
zbMATH DE Number: 1493515
zbMATH Keywords: bipartite crossing number
zbMATH Keywords: lower bounds
zbMATH Keywords: Menger's theorem
zbMATH Keywords: isoperimetric inequalities
zbMATH Keywords: Laplacian eigenvalues
zbMATH Keywords: mesh
zbMATH Keywords: hypercube
MaRDI profile type: Publication
cites work: Edge isoperimetric theorems for integer point arrays
cites work: A framework for solving VLSI graph layout problems
cites work: Q3726125
cites work: Edge-isoperimetric inequalities in the grid
cites work: Matchings and paths in the cube
cites work: Q5691133
cites work: On induced subgraphs of the cube
cites work: Algorithms for drawing graphs: An annotated bibliography
cites work: Edge crossings in drawings of bipartite graphs
cites work: Crossing Number Problems
cites work: Q5501843
cites work: Crossing Number is NP-Complete
cites work: Determinants, Permanents and Bipartite Graphs
cites work: Q5677508
cites work: Optimal Assignments of Numbers to Vertices
cites work: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
cites work: Optimal linear labelings and eigenvalues of graphs
cites work: Q3997942
cites work: A tabu search algorithm for the bipartite drawing problem
cites work: Q3821602
cites work: Q3893961
cites work: Q4339095
cites work: On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem
cites work: Q4352316
cites work: Bipartite permutation graphs
cites work: Q3216652
cites work: Crossing Theory and Hierarchy Mapping
cites work: A SPECIAL CROSSING NUMBER FOR BIPARTITE GRAPHS: A RESEARCH PROBLEM
full work available at URL: s0304-3975(99)00285-6
OpenAlex ID: W2035922087
Recommended article: Graph Drawing
Recommended article: Q3043708
Recommended article: Q3821602
Recommended article: A lower bound for the crossing number ofCm � Cn
Recommended article: Q3139731
Recommended article: A Better Bound for the Pair-Crossing Number
Recommended article: Q5405504
Recommended article: New upper bounds for the crossing numbers of crossing-critical graphs
Recommended article: A lower bound for the rectilinear crossing number
Recommended article: A lower bound on the crossing number of uniform hypergraphs
description: scientific article; zbMATH DE number 1493515