scientific article; zbMATH DE number 7278018

DOI10.4230/LIPICS.ISAAC.2017.13MaRDI QIDQ5136229zbMATHFDO

Authors Markus Chimani, Martin Derka, Petra Mutzel, Therese Biedl

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1612.03854

zbMATH Keywords

crossing numbergraphs with bounded pathwidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Crossing number for graphs with bounded pathwidth
• Crossing-number critical graphs have bounded path-width
• scientific article; zbMATH DE number 2084270
• Crossing numbers for certain distance graphs
• Crossing numbers of graphs
• The Crossing Number of Graphs: Theory and Computation
• Crossing numbers of beyond-planar graphs
• Crossing numbers of beyond-planar graphs
• Crossing number and weighted crossing number of near-planar graphs
• Crossing and Weighted Crossing Number of Near-Planar Graphs

Cites work

• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An algorithm for the graph crossing number problem
• Approximating the Crossing Number of Toroidal Graphs
• Approximating the crossing number of graphs embeddable in any orientable surface
• Approximating the rectilinear crossing number
• Computing crossing numbers in quadratic time
• Crossing number and weighted crossing number of near-planar graphs
• Crossing-number critical graphs have bounded path-width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Hardness of approximation for crossing number
• Inserting multiple edges into a planar graph
• On the crossing numbers of Cartesian products with paths
• Planar decompositions and the crossing number of graphs with an excluded minor
• The crossing number of K₁₁ is 100
• The crossing number of K5,n
• The crossing number of \(P(N,3)\)
• The crossing number of a projective graph is quadratic in the face-width
• The crossing numbers of products of path with graphs of order six
• The graph crossing number and its variants: a survey
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations
• Vertex insertion approximates the crossing number of apex graphs

Cited in

(5)

• Crossing numbers and stress of random graphs
• Crossing number for graphs with bounded pathwidth
• Crossing Numbers and Cutwidths
• Exact crossing number parameterized by vertex cover
• Orthogonal tree decompositions of graphs

This page was built for publication:

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