Buchumschlag

Charting the Diameter Computation Landscape on Intersection Graphs in the Plane

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chan, Timothy M., Chang, Hsien-Chih, Gao, Jie, Kisfaludi-Bak, Sándor, Le, Hung, Zheng, Da Wei
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Geometry
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
von: Kisfaludi-Bak, Sándor, 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)

Recognizing Subgraphs of Regular Tilings
von: Ingervo, Eliel, et al.
Veröffentlicht: (2026)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
von: de Berg, Mark, et al.
Veröffentlicht: (2026)

Realizing Metric Spaces with Convex Obstacles
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2025)

A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2023)

Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2025)

Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
von: Chan, Timothy M., et al.
Veröffentlicht: (2024)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2020)

Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2025)

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
von: Kisfaludi-Bak, Sándor, et al.
Veröffentlicht: (2026)

Computing the Girth of a Segment Intersection Graph
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)

Euclidean TSP in Narrow Strips
von: Alkema, Henk, et al.
Veröffentlicht: (2020)

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

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

Structure and Independence in Hyperbolic Uniform Disk Graphs
von: Bläsius, Thomas, et al.
Veröffentlicht: (2024)

Touring a Sequence of Orthogonal Polygons
von: Casel, Katrin, et al.
Veröffentlicht: (2026)

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

Optimal Euclidean Tree Covers
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Dynamic Geometric Connectivity in the Plane with Constant Query Time
von: Chan, Timothy M., et al.
Veröffentlicht: (2024)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
von: Duraj, Lech, et al.
Veröffentlicht: (2023)

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
von: Browne, Reilly, et al.
Veröffentlicht: (2026)

Covering the Euclidean Plane by a Pair of Trees
von: Le, Hung, et al.
Veröffentlicht: (2025)

A Practical Approach for Computing the Diameter of a Point Set
von: Har-Peled, Sariel
Veröffentlicht: (2025)

On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects
von: Chan, Timothy M., et al.
Veröffentlicht: (2024)

On Computing Vertex Connectivity of 1-Plane Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2022)

Triangulating a Polygon with Holes in Optimal (Deterministic) Time
von: Chan, Timothy M.
Veröffentlicht: (2026)

Approximating Densest Subgraph in Geometric Intersection Graphs
von: Har-Peled, Sariel, et al.
Veröffentlicht: (2024)

Star-Based Separators for Intersection Graphs of $c$-Colored Pseudo-Segments
von: de Berg, M., et al.
Veröffentlicht: (2025)

Smallest Intersecting and Enclosing Balls
von: Zheng, Jiaqi, et al.
Veröffentlicht: (2025)

Hop-Spanners for Geometric Intersection Graphs
von: Conroy, Jonathan B., et al.
Veröffentlicht: (2021)

Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2024)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)

Constant Workspace Algorithms for Computing Relative Hulls in the Plane
von: Chhabra, Himanshu, et al.
Veröffentlicht: (2024)

Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion
von: Honorato-Droguett, Nicolás, et al.
Veröffentlicht: (2025)

Shortest Path Separators in Unit Disk Graphs
von: Harb, Elfarouk, et al.
Veröffentlicht: (2024)

Fully Dynamic Geometric Vertex Cover and Matching
von: Bhore, Sujoy, et al.
Veröffentlicht: (2024)