On graph crossing number and edge planarization

MaRDI QIDQ5365099zbMATH OpenFDO

Authors Julia Chuzhoy, Yury Makarychev, Anastasios Sidiropoulos

Publication date 29 September 2017

Full work available at URL https://arxiv.org/abs/1010.3976, http://dl.acm.org/citation.cfm?id=2133116

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An algorithm for the graph crossing number problem
• On the Crossing Number of Almost Planar Graphs
• Approximating the Crossing Number of Apex Graphs

Cited in

(38)

• A successful concept for measuring non-planarity of graphs: The crossing number.
• Planar decompositions and the crossing number of graphs with an excluded minor
• On the Size of Planarly Connected Crossing Graphs
• An effective crossing minimisation heuristic based on star insertion
• Improved approximations of crossings in graph drawings
• scientific article; zbMATH DE number 3646924 (Why is no real title available?)
• On the Minimum Cut of Planarizations
• On the Crossing Number of Almost Planar Graphs
• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Approximating the Crossing Number of Apex Graphs
• Approximation algorithms for Euler genus and related problems
• The effect of planarization on width
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Counting Plane Graphs: Cross-Graph Charging Schemes
• The effect of planarization on width
• Crossing Numbers of Beyond-Planar Graphs Revisited
• Connecting the dots (with minimum crossings)
• Hypergraph and minor crossing number problems
• A Census of Plane Graphs with Polyline Edges
• An algorithm for the graph crossing number problem
• Crossing number and weighted crossing number of near-planar graphs
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Advances in the planarization method: effective multiple edge insertions
• Advances in the planarization method: effective multiple edge insertions
• Crossing minimization in perturbed drawings
• Algorithms and Computation
• Crossing minimization in perturbed drawings
• Crossing numbers of beyond-planar graphs
• Approximating the Bundled Crossing Number
• Inserting Multiple Edges into a Planar Graph
• Parameterised partially-predrawn crossing number
• Vertex insertion approximates the crossing number of apex graphs
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Approximating the crossing number of dense graphs (poster abstract)
• An algorithmic meta-theorem for graph modification to planarity and FOL
• An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers
• On the obfuscation complexity of planar graphs

This page was built for publication: On graph crossing number and edge planarization

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