On the one-sided crossing minimization in a bipartite graph with large degrees

DOI10.1016/j.tcs.2004.10.042zbMath1142.68461OpenAlexW2017361734MaRDI QIDQ1770400

Hiroshi Nagamochi

Publication date: 6 April 2005

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.042

zbMATH Keywords

Approximation algorithmGraph drawingRandomized algorithmBipartite graph2-layered drawingEdge crossing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

The slotted online one-sided crossing minimization problem on 2-regular graphs ⋮ A variable depth neighborhood search algorithm for the min-max arc crossing problem ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization

Cites Work

• Edge crossings in drawings of bipartite graphs
• New bounds on the barycenter heuristic for bipartite graph drawing.
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Crossing Number is NP-Complete
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• Trees with Hamiltonian square
• Graph Drawing
• Graph Drawing
• Experiments on drawing 2-level hierarchical graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item