Cover Image

Crossing Number is NP-hard for Constant Path-width (and Tree-width)

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hliněný, Petr, Khazaliya, Liana
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry Discrete Mathematics 68R10
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs
by: Hliněný, Petr
Published: (2023)

Stack and Queue Numbers of Graphs Revisited
by: Hliněný, Petr, et al.
Published: (2023)

Hereditary Graph Product Structure and $\cal H$-clique-width
by: Hliněný, Petr, et al.
Published: (2024)

Note on Min-k-Planar Drawings of Graphs
by: Hliněný, Petr, et al.
Published: (2024)

Minimizing an Uncrossed Collection of Drawings
by: Hliněný, Petr, et al.
Published: (2023)

On the Uncrossed Number of Graphs
by: Balko, Martin, et al.
Published: (2024)

A Unified FPT Framework for Crossing Number Problems
by: de Verdière, Éric Colin, et al.
Published: (2024)

Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach
by: Chimani, Markus, et al.
Published: (2024)

Rectangular Duals on the Cylinder and the Torus
by: Biedl, Therese, et al.
Published: (2025)

Exact Wirelength of Embedding 3-Ary n-Cubes into certain Cylinders and Trees
by: S, Rajeshwari, et al.
Published: (2022)

Unbent Collections of Orthogonal Drawings
by: Antić, Todor, et al.
Published: (2025)

Some Counterexamples for Compatible Triangulations
by: Barnson, Cody, et al.
Published: (2016)

General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number
by: Charvy, Gaspard, et al.
Published: (2025)

A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
by: Asiri, Zayed, et al.
Published: (2024)

Shortest Paths in a Weighted Simplicial Complex
by: Chakraborty, Sukrit, et al.
Published: (2025)

Grid-drawings of graphs in three-dimensions
by: Balogh, Jozsef, et al.
Published: (2024)

Harmonious Colorings: bounds, heuristics and integer-linear formulations
by: Araújo, Júlio, et al.
Published: (2026)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
by: Mkrtchyan, Vahan
Published: (2024)

Visualizing Geophylogenies -- Internal and External Labeling with Phylogenetic Tree Constraints
by: Klawitter, Jonathan, et al.
Published: (2023)

A framework for distributed discrete evacuation strategies
by: Borowiecki, Piotr, et al.
Published: (2025)

Fast winning strategies for the attacker in eternal domination
by: Bagan, Guillaume, et al.
Published: (2024)

Extremal Results on Conflict-free Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2023)

Symmetric properties and two variants of shuffle-cubes
by: Lü, Huazhong, et al.
Published: (2021)

Improved bounds for acyclic coloring parameters
by: Kirousis, Lefteris, et al.
Published: (2022)

Paired many-to-many 2-disjoint path cover of Johnson graphs
by: Liu, Jinhao, et al.
Published: (2025)

Degree Realization by Bipartite Multigraphs
by: Bar-Noy, Amotz, et al.
Published: (2025)

The damage number of the Cartesian product of graphs
by: Huggan, Melissa A., et al.
Published: (2023)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
by: Munaro, Andrea, et al.
Published: (2022)

Optimal Discretization is Fixed-parameter Tractable
by: Kratsch, Stefan, et al.
Published: (2020)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases
by: Meusel, Julia, et al.
Published: (2025)

A Note on Small Percolating Sets on Hypercubes via Generative AI
by: Bérczi, Gergely, et al.
Published: (2024)

Searching by Heterogeneous Agents
by: Dereniowski, Dariusz, et al.
Published: (2021)

On solving basic equations over the semiring of functional digraphs
by: Dennunzio, Alberto, et al.
Published: (2024)

$\mathcal{S}$-adic characterization of minimal dendric shifts
by: Gheeraert, France, et al.
Published: (2022)

Remarks about the Moebius-Kantor graph
by: Knill, Oliver
Published: (2026)

Word-Representability of Graphs with respect to Split Recomposition
by: Dwary, Tithi, et al.
Published: (2024)

An efficient algorithm for generating transmission irregular trees
by: Stošić, Ivan, et al.
Published: (2025)

Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
by: Ghosh, Soumyadip, et al.
Published: (2024)

Towards Characterization of 5-List-Colorability of Toroidal Graphs
by: Dvořák, Zdeněk, et al.
Published: (2024)