Approximating the fixed linear crossing number
From MaRDI portal
Publication:2456999
DOI10.1016/j.dam.2007.05.009zbMath1127.68116OpenAlexW2053535344MaRDI QIDQ2456999
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
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
The 2-page crossing number of \(K_{n}\) ⋮ On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page
Cites Work
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- The book thickness of a graph
- Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
- Algorithms for the fixed linear crossing number problem
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- Outward rotations
- Crossing Minimisation Heuristics for 2-page Drawings
- Single Row Routing
- The bandwidth problem for graphs and matrices—a survey
- Graphs with E Edges Have Pagenumber O(√E)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- The book crossing number of a graph
- An Interior-Point Method for Semidefinite Programming
- Crossing minimization in linear embeddings of graphs
- A Boundary Method for Planar Travelling Salesman Problems
- Sorting Using Networks of Queues and Stacks
- Drawing graphs. Methods and models
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
