One-sided local crossing minimization is NP-hard for forests of high-degree stars (with tight ETH lower bound), solvable in quadratic time for degree-2 stars, and admits a 3-approximation via median heuristic with tie-breaking.
2022.101900
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 5roles
background 1polarities
background 1representative citing papers
Feedback vertex set and feedback edge set are NP-complete on directed graphs of maximum degree 3; on planar digraphs, feedback vertex set is polynomial-time solvable if every vertex has indegree at most 1 or outdegree at most 1 and NP-complete otherwise, with tight degree bounds also given for the 3
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.
Support-weighted partial recentering of maxmin seeds using halfspace depth yields consistent geometric improvement over standard maxmin in planar benchmarks while preserving thresholded H1 summaries.
O(n^3 log n) algorithm computes maximum (weighted) independent sets for disk graphs with all disks on the convex hull, plus O(n^3 log^2 n) for k-dispersion on the same inputs.
citing papers explorer
-
One-Sided Local Crossing Minimization
One-sided local crossing minimization is NP-hard for forests of high-degree stars (with tight ETH lower bound), solvable in quadratic time for degree-2 stars, and admits a 3-approximation via median heuristic with tie-breaking.
-
Feedback Set Problems on Bounded-Degree (Planar) Graphs
Feedback vertex set and feedback edge set are NP-complete on directed graphs of maximum degree 3; on planar digraphs, feedback vertex set is polynomial-time solvable if every vertex has indegree at most 1 or outdegree at most 1 and NP-complete otherwise, with tight degree bounds also given for the 3
-
Visibility Queries in Simple Polygons
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.
-
Local Depth-Based Corrections to Maxmin Landmark Selection for Lazy Witness Persistence
Support-weighted partial recentering of maxmin seeds using halfspace depth yields consistent geometric improvement over standard maxmin in planar benchmarks while preserving thresholded H1 summaries.
-
Maximum Independent Sets in Disk Graphs with Disks in Convex Position
O(n^3 log n) algorithm computes maximum (weighted) independent sets for disk graphs with all disks on the convex hull, plus O(n^3 log^2 n) for k-dispersion on the same inputs.