Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
From MaRDI portal
Publication:3591323
DOI10.1007/11809678_53zbMath1162.68492OpenAlexW2117566233MaRDI QIDQ3591323
Christoph Buchheim, Lanbo Zheng
Publication date: 10 September 2007
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://e-archive.informatik.uni-koeln.de/522/2/zaik2006-522.pdf
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
The Crossing Number of the Cone of a Graph ⋮ The 2-page crossing number of \(K_{n}\) ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ The Crossing Number of the Cone of a Graph ⋮ Book drawings of complete bipartite graphs ⋮ Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation ⋮ The complexity of SIMPLE MAX-CUT on comparability graphs ⋮ Revising Johnson's table for the 21st century
This page was built for publication: Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
