Recent advances in exact crossing minimization (extended abstract)

DOI10.1016/J.ENDM.2008.06.015MaRDI QIDQ5300976zbMATH OpenOpenAlexWikidataFDO

Authors Petra Mutzel

Publication date 28 June 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2008.06.015

zbMATH Keywords

integer linear programmingbranch-and-cutcrossing number

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Integer programming (90C10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Graph Drawing
• A New Approach to Exact Crossing Minimization
• A branch-and-cut approach to the crossing number problem
• Experiments on exact crossing minimization using column generation
• SOFSEM 2005: Theory and Practice of Computer Science

Cites work

• scientific article; zbMATH DE number 3394160 (Why is no real title available?)
• A Depth-First-Search Characterization of Planarity
• A New Approach to Exact Crossing Minimization
• A branch-and-cut approach to the crossing number problem
• Computing crossing numbers in quadratic time
• Experiments on Exact Crossing Minimization Using Column Generation
• Graph Drawing
• On Cotree-Critical and DFS Cotree-Critical Graphs
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• The crossing number of K₁₁ is 100

Cited in

(11)

• A branch-and-cut approach to the crossing number problem
• A New Approach to Exact Crossing Minimization
• Graph Drawing
• Experiments on Exact Crossing Minimization Using Column Generation
• An algorithmic development to minimize crossings in electronic circuits
• An SDP approach to multi-level crossing minimization
• An evolutionary formulation of the crossing number problem
• Facets in the crossing number polytope
• Simple realizability of complete abstract topological graphs simplified
• scientific article; zbMATH DE number 2170413 (Why is no real title available?)
• Experiments on exact crossing minimization using column generation

Describes a project that uses

Uses Software

• PIGALE

This page was built for publication: Recent advances in exact crossing minimization (extended abstract)

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