Triangles and girth in disk graphs and transmission graphs

DOI10.4230/LIPICS.ESA.2019.64MaRDI QIDQ5075809zbMATH OpenFDO

Authors Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1907.01980

zbMATH Keywords

triangledisk graphgirthtransmission graph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Approximation and Online Algorithms
• Shortest paths in intersection graphs of unit disks
• Approximate Distance Queries in Disk Graphs
• Spanners for Geometric Intersection Graphs
• Minimum cuts in geometric intersection graphs

Cites work

• scientific article; zbMATH DE number 6850341 (Why is no real title available?)
• A shortest cycle for each vertex of a graph
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
• Adding range restriction capability to dynamic data structures
• Computational geometry. Algorithms and applications.
• Computing hereditary convex structures
• Delaunay triangulations in O (sort( n )) time and more
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Geometric applications of a randomized optimization technique
• Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• On minimal Eulerian graphs
• Powers of tensors and fast matrix multiplication
• Preprocessing imprecise points for Delaunay triangulation: simplified and extended
• Recognizing a DOG is hard, but not when it is thin and unit
• Spanners and Reachability Oracles for Directed Transmission Graphs
• Spanners for directed transmission graphs
• Subcubic equivalences between path, matrix, and triangle problems

Cited in

(2)

• Dynamic connectivity in disk graphs
• Maximum matchings in geometric intersection graphs

This page was built for publication: Triangles and girth in disk graphs and transmission graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075809)