scientific article; zbMATH DE number 7278018

DOI10.4230/LIPICS.ISAAC.2017.13zbMATH Open1457.68204arXiv1612.03854MaRDI QIDQ5136229FDOQ5136229

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

Title of this publication is not available (Why is that?)

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

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)

Cites Work

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

Cited In (5)

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

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)