Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem

DOI10.1007/11809678_53MaRDI QIDQ3591323zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• Algorithms for the fixed linear crossing number problem
• An analysis of some linear graph layout heuristics
• Approximating the fixed linear crossing number
• A branch-and-cut approach to the crossing number problem
• A New Approach to Exact Crossing Minimization

Cited in

(14)

• Algorithms for the fixed linear crossing number problem
• Revising Johnson's table for the 21st century
• Complexity-separating graph classes for vertex, edge and total colouring
• An improved fixed-parameter algorithm for max-cut parameterized by crossing number
• The 2-page crossing number of \(K_{n}\)
• Book drawings of complete bipartite graphs
• Approximating the fixed linear crossing number
• An analysis of some linear graph layout heuristics
• The crossing number of the cone of a graph
• A variation on the min cut linear arrangement problem
• The crossing number of the cone of a graph
• The complexity of SIMPLE MAX-CUT on comparability graphs
• Parameterized algorithms for fixed-order book drawing with few crossings per edge
• Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation

This page was built for publication: Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3591323)