On Bipartite Drawings and the Linear Arrangement Problem

DOI10.1137/S0097539797331671zbMath0980.68080OpenAlexW2035359116MaRDI QIDQ2706134

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

Publication date: 19 March 2001

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539797331671

zbMATH Keywords

approximation algorithmsbipartite crossing numberlinear arrangementbiplanar graphbipartite drawing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Applications of graph theory to circuits and networks (94C15)

Related Items (14)

A faster fixed parameter algorithm for two-layer crossing minimization ⋮ The optimal tenement allocation for reducing traffic burden ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Two-layer planarization parameterized by feedback edge set ⋮ Molecular solution to the optimal linear arrangement problem based on DNA computation ⋮ Graph parameters measuring neighbourhoods in graphs-bounds and applications ⋮ Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization ⋮ Multistart search for the cyclic cutwidth minimization problem ⋮ Approximation algorithms for minimizing edge crossings in radial drawings ⋮ A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem ⋮ k-Level Crossing Minimization Is NP-Hard for Trees ⋮ A linear edge kernel for two-layer crossing minimization ⋮ Optimal one-page tree embeddings in linear time ⋮ Bounds of the sum of edge lengths in linear arrangements of trees

This page was built for publication: On Bipartite Drawings and the Linear Arrangement Problem