A unified FPT framework reduces many crossing-number variants on surfaces to simplicial-complex embeddability, parameterized by genus and crossing bound, with linear or quadratic dependence.
13 Petr Hliněný and Csenge Lili Ködmön
4 Pith papers cite this work, alongside 81 external citations. Polarity classification is still indexing.
4
Pith papers citing it
81
external citations · Crossref
representative citing papers
Graphs of treewidth k satisfy α_c(G) ≥ c/(c+k+1)n with matching upper-bound constructions; the bound improves to c/(c+k)n when c≤2 or k=1 and to 5/9 n when c=3 and k=2.
Proves NP-hardness of recognizing min-1-planar graphs.
Every 4-connected optimal 2-planar graph is Hamiltonian-connected, with the 4-connectedness condition being sharp via infinitely many 3-connected counterexamples that are non-Hamiltonian.
citing papers explorer
-
A Unified FPT Framework for Crossing Number Problems
A unified FPT framework reduces many crossing-number variants on surfaces to simplicial-complex embeddability, parameterized by genus and crossing bound, with linear or quadratic dependence.
-
Clustered independence and bounded treewidth
Graphs of treewidth k satisfy α_c(G) ≥ c/(c+k+1)n with matching upper-bound constructions; the bound improves to c/(c+k)n when c≤2 or k=1 and to 5/9 n when c=3 and k=2.
-
Min-1-Planarity is NP-Hard
Proves NP-hardness of recognizing min-1-planar graphs.
-
A note on optimal 2-planar graphs
Every 4-connected optimal 2-planar graph is Hamiltonian-connected, with the 4-connectedness condition being sharp via infinitely many 3-connected counterexamples that are non-Hamiltonian.