Buchumschlag

Sparse Outerstring Graphs Have Logarithmic Treewidth

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	An, Shinwoo, Oh, Eunjin, Xue, Jie
Format:	Preprint
Veröffentlicht:	2024
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

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
von: An, Shinwoo, 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)

Dynamic parameterized problems on unit disk graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

Visualizing Treewidth
von: Chiu, Alvin, et al.
Veröffentlicht: (2025)

Range Counting Oracles for Geometric Problems
von: Driemel, Anne, et al.
Veröffentlicht: (2025)

Visibility Queries in Simple Polygons
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

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

Dynamic Treewidth in Logarithmic Time
von: Korhonen, Tuukka
Veröffentlicht: (2025)

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

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

Triangle Detection in Worst-Case Sparse Graphs via Local Sketching
von: Duan, Hongyi, et al.
Veröffentlicht: (2025)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
von: Maus, Victor, et al.
Veröffentlicht: (2026)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

Algorithms for Halfplane Coverage and Related Problems
von: Wang, Haitao, et al.
Veröffentlicht: (2024)

Enclosing Points with Geometric Objects
von: Chan, Timothy M., et al.
Veröffentlicht: (2024)

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

Scattering and Sparse Partitions, and their Applications
von: Filtser, Arnold
Veröffentlicht: (2020)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
von: Filtser, Arnold
Veröffentlicht: (2024)

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)

Mimicking Networks for Constrained Multicuts in Hypergraphs
von: Cho, Kyungjin, et al.
Veröffentlicht: (2024)

Parameterized Approximation of Rectangle Stabbing
von: Chu, Huairui, et al.
Veröffentlicht: (2026)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, 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)

Dynamic Connectivity in Disk Graphs
von: Baumann, Alexander, et al.
Veröffentlicht: (2021)

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)

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

Unit-length Rectangular Drawings of Graphs
von: Alegria, Carlos, et al.
Veröffentlicht: (2022)

Parameterized Geometric Graph Modification with Disk Scaling
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

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

Computing Maximum Cliques in Unit Disk Graphs
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2025)

Generalized Graph Packing Problems Parameterized by Treewidth
von: Esmer, Barış Can, et al.
Veröffentlicht: (2025)

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

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

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2024)

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)