A new lower bound for the bipartite crossing number with applications

DOI10.1016/S0304-3975(99)00285-6zbMath0946.68102OpenAlexW2035922087MaRDI QIDQ1575746

Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrt'o

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00285-6

zbMATH Keywords

hypercubeisoperimetric inequalitiesLaplacian eigenvalueslower boundsmeshbipartite crossing numberMenger's theorem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items

Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• Bipartite permutation graphs
• On induced subgraphs of the cube
• Edge-isoperimetric inequalities in the grid
• Optimal linear labelings and eigenvalues of graphs
• Edge crossings in drawings of bipartite graphs
• Algorithms for drawing graphs: An annotated bibliography
• Matchings and paths in the cube
• A tabu search algorithm for the bipartite drawing problem
• Edge isoperimetric theorems for integer point arrays
• Crossing Number is NP-Complete
• Crossing Theory and Hierarchy Mapping
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem
• Determinants, Permanents and Bipartite Graphs
• Optimal Assignments of Numbers to Vertices
• A SPECIAL CROSSING NUMBER FOR BIPARTITE GRAPHS: A RESEARCH PROBLEM
• Crossing Number Problems