Buchumschlag

Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bjerkevik, Håvard Bakke, Dorfer, Joseph, Kleist, Linda, Ueckerdt, Torsten, Vogtenhuber, Birgit
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Geometry Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Flipping Non-Crossing Spanning Trees
von: Bjerkevik, Håvard Bakke, et al.
Veröffentlicht: (2024)

Constrained Flips in Plane Spanning Trees
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2025)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
von: Dorfer, Joseph
Veröffentlicht: (2026)

Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2026)

Computing $p$-presentation distances is hard
von: Bjerkevik, Håvard Bakke, et al.
Veröffentlicht: (2024)

Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2023)

Crossing and non-crossing families
von: Antić, Todor, et al.
Veröffentlicht: (2025)

Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2024)

Crossing Number of 3-Plane Drawings
von: Goetze, Miriam, et al.
Veröffentlicht: (2025)

Edge densities of drawings of graphs with one forbidden cell
von: Hahn, Benedikt, et al.
Veröffentlicht: (2025)

Reeb Graph of Sample Thickenings
von: Bjerkevik, Håvard Bakke, et al.
Veröffentlicht: (2025)

A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2025)

On the geometric $k$-colored crossing number of $K_n$
von: Hahn, Benedikt, et al.
Veröffentlicht: (2025)

On the Connectivity of the Flip Graph of Plane Spanning Paths
von: Kleist, Linda, et al.
Veröffentlicht: (2024)

Characterizing and Recognizing Twistedness
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2025)

Flipping odd matchings in geometric and combinatorial settings
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2025)

Intersection Graphs with and without Product Structure
von: Merker, Laura, et al.
Veröffentlicht: (2024)

Stabilizing decomposition of multiparameter persistence modules
von: Bjerkevik, Håvard Bakke
Veröffentlicht: (2023)

Flips in Odd Matchings
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2024)

Counting Barcodes with the same Betti Curve
von: Ashley, Henry, et al.
Veröffentlicht: (2026)

Adjacency Graphs of Polyhedral Surfaces
von: Arseneva, Elena, et al.
Veröffentlicht: (2021)

Improved Lower Bound on the Number of Pseudoline Arrangements
von: Dallant, Justin
Veröffentlicht: (2024)

Rainbow polygons for colored point sets in the plane
von: Flores-Peñaloza, David, et al.
Veröffentlicht: (2020)

Minimum Plane Bichromatic Spanning Trees
von: Akitaya, Hugo A., et al.
Veröffentlicht: (2024)

Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane
von: Draganov, Ondřej, et al.
Veröffentlicht: (2025)

Computing the EHZ capacity is NP-hard
von: Leipold, Karla, et al.
Veröffentlicht: (2024)

Upper Bounds for $s$-Distance Subspaces
von: Wang, LiXia, et al.
Veröffentlicht: (2025)

Distinct Distances Between a Line and Strip
von: Das, Sanjana, et al.
Veröffentlicht: (2025)

The r-Dynamic Chromatic Number is Bounded in the Strong 2-Coloring Number
von: Goetze, Miriam, et al.
Veröffentlicht: (2025)

Bounding and computing obstacle numbers of graphs
von: Balko, Martin, et al.
Veröffentlicht: (2022)

Drawings of Complete Multipartite Graphs Up to Triangle Flips
von: Aichholzer, Oswin, et al.
Veröffentlicht: (2023)

A Note on Polychromatic Colorings of Shift-Chains
von: Ueckerdt, Torsten
Veröffentlicht: (2024)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Flips in Two-dimensional Hypertriangulations
von: Edelsbrunner, Herbert, et al.
Veröffentlicht: (2022)

The Price of Connectivity Augmentation on Planar Graphs
von: Akitaya, Hugo A., et al.
Veröffentlicht: (2025)

Bounding the number of holes required for folding rectangular polyominoes into cubes
von: Lehner, Florian, et al.
Veröffentlicht: (2025)

Rectilinear Crossing Number of Graphs Excluding Single-Crossing Graphs as Minors
von: Dujmović, Vida, et al.
Veröffentlicht: (2024)

Monotonically Decreasing the Number of Directed 3-Cycles via Edge-Flips?
von: Bom, David, et al.
Veröffentlicht: (2025)

Crossing lemmas for $k$-systems of arcs
von: Hubard, Alfredo, et al.
Veröffentlicht: (2024)

On the Uncrossed Number of Graphs
von: Balko, Martin, et al.
Veröffentlicht: (2024)