Crossing number for graphs with bounded pathwidth

DOI10.1007/s00453-019-00653-xzbMath1433.68280OpenAlexW3000010299WikidataQ126378314 ScholiaQ126378314MaRDI QIDQ1986966

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

Publication date: 9 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8257/

zbMATH Keywords

complexityapproximationgraph algorithmscrossing numberpathwidth

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 (4)

Parameterized analysis and crossing minimization problems ⋮ Inserting Multiple Edges into a Planar Graph ⋮ 2-Layer Graph Drawings with Bounded Pathwidth ⋮ On Numerical Invariant of Graph

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• How to draw a planar graph on a grid
• On the crossing numbers of Cartesian products with paths
• The crossing number of a projective graph is quadratic in the face-width
• Some provably hard crossing number problems
• 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
• 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
• Crossing-Free Subgraphs
• 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
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• The crossing number of K5,n
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Crossing number for graphs with bounded pathwidth