Buchumschlag

Min-1-Planarity is NP-Hard

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Okada, Yuto
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Geometry Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

2-Layer Fan-Planarity in Polynomial Time
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

Recognizing 2-Layer and Outer $k$-Planar Graphs
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2024)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
von: Grandoni, Fabrizio, et al.
Veröffentlicht: (2026)

Ranking and Unranking of the Planar Embeddings of a Planar Graph
von: Di Battista, Giuseppe, et al.
Veröffentlicht: (2024)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

A Framework for the Design of Efficient Diversification Algorithms to NP-Hard Problems
von: Gálvez, Waldo, et al.
Veröffentlicht: (2025)

Upward-Planar Drawings with Bounded Span
von: Angelini, Patrizio, et al.
Veröffentlicht: (2026)

Weakly Leveled Planarity with Bounded Span
von: Bekos, Michael, et al.
Veröffentlicht: (2024)

On Planar Straight-Line Dominance Drawings
von: Angelini, Patrizio, et al.
Veröffentlicht: (2025)

Clustered Planarity Variants for Level Graphs
von: Fink, Simon D., et al.
Veröffentlicht: (2024)

Structural Parameterizations of $k$-Planarity
von: Gima, Tatsuya, et al.
Veröffentlicht: (2025)

Exact Algorithms for Clustered Planarity with Linear Saturators
von: Da Lozzo, Giordano, et al.
Veröffentlicht: (2024)

Morphing Planar Graph Drawings Through 3D
von: Buchin, Kevin, et al.
Veröffentlicht: (2022)

Incremental Planar Nearest Neighbor Queries with Optimal Query Time
von: Iacono, John, et al.
Veröffentlicht: (2025)

Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
von: Klemz, Boris, et al.
Veröffentlicht: (2024)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)

Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
von: Park, Seongbin, et al.
Veröffentlicht: (2026)

The Impossibility of Simultaneous Time and I/O Optimality for The Planar Maxima and Convex Hull Problems
von: Afshani, Peyman, et al.
Veröffentlicht: (2026)

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
von: Cabello, Sergio, et al.
Veröffentlicht: (2025)

A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
von: Gusain, Rachana, et al.
Veröffentlicht: (2025)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
von: Lynch, Jayson, et al.
Veröffentlicht: (2025)

Hardness of Median and Center in the Ulam Metric
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

Upward Pointset Embeddings of Planar st-Graphs
von: Alegria, Carlos, et al.
Veröffentlicht: (2024)

Computational Hardness of Private Coreset
von: Ghazi, Badih, et al.
Veröffentlicht: (2026)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
von: Kluk, Kacper, et al.
Veröffentlicht: (2026)

Distance Approximating Minors for Planar and Minor-Free Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

O(1)-Distortion Planar Emulators for String Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2025)

Planar Network Diversion
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Hardness of High-Dimensional Linear Classification
von: Munteanu, Alexander, et al.
Veröffentlicht: (2026)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

On Approximability of $\ell_2^2$ Min-Sum Clustering
von: S., Karthik C., et al.
Veröffentlicht: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
von: Di Battista, Giuseppe, et al.
Veröffentlicht: (2021)

Spanner for the $0/1/\infty$ weighted region problem
von: Gudmundsson, Joachim, et al.
Veröffentlicht: (2024)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
von: de Berg, Sarita, et al.
Veröffentlicht: (2026)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

A face cover perspective to $\ell_1$ embeddings of planar graphs
von: Filtser, Arnold
Veröffentlicht: (2019)

Sequential non-determinism in tile self-assembly: a general framework and an application to efficient temperature-1 self-assembly of squares
von: Furcy, David, et al.
Veröffentlicht: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)