Approximating the fixed linear crossing number

DOI10.1016/J.DAM.2007.05.009MaRDI QIDQ2456999zbMATH OpenOpenAlexFDO

Authors Brendan Mumey, Robert J. Cimikowski

Publication date 29 October 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.05.009

zbMATH Keywords

approximation algorithmcrossing numberrandomized algorithm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Algorithms for the fixed linear crossing number problem
• An analysis of some linear graph layout heuristics
• An algorithm for the graph crossing number problem
• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• Approximating the maximum rectilinear crossing number

Cites work

• A Boundary Method for Planar Travelling Salesman Problems
• Algorithms for the fixed linear crossing number problem
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• An Interior-Point Method for Semidefinite Programming
• Crossing Minimisation Heuristics for 2-page Drawings
• Crossing minimization in linear embeddings of graphs
• Drawing graphs. Methods and models
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• Graphs with E Edges Have Pagenumber O(√E)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3980512 (Why is no real title available?)
• scientific article; zbMATH DE number 15256 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 1261818 (Why is no real title available?)
• scientific article; zbMATH DE number 1054768 (Why is no real title available?)
• scientific article; zbMATH DE number 780784 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• Single Row Routing
• Sorting Using Networks of Queues and Stacks
• The bandwidth problem for graphs and matrices—a survey
• The book crossing number of a graph
• The book thickness of a graph

Cited in

(13)

• Algorithms for the fixed linear crossing number problem
• Computing crossing numbers in quadratic time
• On the crossing number of 2-page book drawings of K_n with prescribed number of edges in each page
• Approximating the rectilinear crossing number
• The 2-page crossing number of \(K_{n}\)
• Inapproximability ratios for crossing number
• An analysis of some linear graph layout heuristics
• On the Pseudolinear Crossing Number
• Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
• An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants
• Edge crossings in random linear arrangements
• 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: Approximating the fixed linear crossing number

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