Exact crossing number parameterized by vertex cover
From MaRDI portal
Publication:2206863
DOI10.1007/978-3-030-35802-0_24OpenAlexW2990235292MaRDI QIDQ2206863
Petr Hliněný, Abhisekh Sankaran
Publication date: 26 October 2020
Full work available at URL: https://arxiv.org/abs/1906.06048
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (8)
Parameterized Algorithms for Queue Layouts ⋮ Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number ⋮ Fixed-parameter tractability for book drawing with bounded number of crossings per edge ⋮ Parameterized analysis and crossing minimization problems ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Parameterized complexity of graph planarity with restricted cyclic orders ⋮ Parameterized complexity of graph planarity with restricted cyclic orders
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex insertion approximates the crossing number of apex graphs
- A framework for solving VLSI graph layout problems
- Computing crossing numbers in quadratic time
- Hardness of approximation for crossing number
- Zarankiewicz's conjecture is finite for each fixed \(m\)
- A tighter insertion-based approximation of the crossing number
- Approximating the rectilinear crossing number
- Crossing Number is NP-Complete
- The crossing number of a projective graph is quadratic in the face–width
- On the Crossing Number of Almost Planar Graphs
- Crossing and Weighted Crossing Number of Near-Planar Graphs
- Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- An algorithm for the graph crossing number problem
- Crossing minimization in perturbed drawings
This page was built for publication: Exact crossing number parameterized by vertex cover
