scientific article; zbMATH DE number 7278018

DOI10.4230/LIPIcs.ISAAC.2017.13zbMath1457.68204arXiv1612.03854MaRDI QIDQ5136229

Markus Chimani, Martin Derka, Petra Mutzel, Therese C. Biedl

Publication date: 25 November 2020

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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)

Related Items

Exact crossing number parameterized by vertex cover ⋮ Crossing numbers and stress of random graphs ⋮ Crossing number for graphs with bounded pathwidth

Cites Work

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

This page was built for publication: