On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem

DOI10.1007/3-540-63307-3_48zbMath1497.68397OpenAlexW1490218556MaRDI QIDQ5096926

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

Publication date: 19 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63307-3_48

zbMATH Keywords

bipartite graphpolynomial-time approximation algorithmmedian propertylinear-time algorithmlinear arrangement

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex degrees (05C07) Signed and weighted graphs (05C22)

Related Items (2)

On the complexity of the maximum biplanar subgraph problem ⋮ A new lower bound for the bipartite crossing number with applications

Cites Work

• On optimal linear arrangements of trees
• Bipartite permutation graphs
• Optimal linear labelings and eigenvalues of graphs
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• Algorithms for drawing graphs: An annotated bibliography
• Crossing Number is NP-Complete
• Crossing Theory and Hierarchy Mapping
• A Minimum Linear Arrangement Algorithm for Undirected Trees
• Graph layout problems
• Determinants, Permanents and Bipartite Graphs
• A SPECIAL CROSSING NUMBER FOR BIPARTITE GRAPHS: A RESEARCH PROBLEM
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem