Efficient Algorithms and Innovative Techniques in Graph Theory

The recent developments in the research area of graph theory and algorithms have shown significant advancements in several key areas. Notably, there has been a strong focus on optimizing subgraph counting algorithms for bounded degeneracy graphs, with new subquadratic time solutions being proposed. This trend extends to the realm of weight-balanced trees, where novel grand-children balanced trees have been introduced, offering improved node depth and height characteristics. Additionally, there is a growing interest in hypergraph partitioning, with a new spectral coarsening approach demonstrating state-of-the-art performance in partitioning large-scale hypergraphs. The field is also witnessing advancements in graph drawing algorithms, particularly with the use of cubic Bézier curves for planar and 1-planar graphs, ensuring bounded curvature and efficient computation times. Furthermore, there are notable strides in dynamic graph algorithms, including distance oracles and decremental reachability, with subquadratic time solutions for minor-free digraphs. These developments collectively indicate a shift towards more efficient, practical, and theoretically grounded algorithms across various graph-related problems.

Noteworthy papers include 'Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs,' which introduces a framework for subquadratic algorithms, and 'SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning,' which presents a novel multilevel spectral framework for hypergraph partitioning. These contributions significantly advance the field by addressing long-standing challenges with innovative solutions.

Sources

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs

Grand-children weight-balanced binary search trees

SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning

Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring

Drawing Planar Graphs and 1-Planar Graphs Using Cubic B\'ezier Curves with Bounded Curvature

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more

Even Faster $(\Delta + 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains

Quasi-linear distance query reconstruction for graphs of bounded treelength

Reconfiguring homomorphisms to reflexive graphs via a simple reduction

Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing

Membership Testing for Semantic Regular Expressions

Graph Exploration: The Impact of a Distance Constraint

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal

A Simple Partially Embedded Planarity Test Based on Vertex-Addition

Built with on top of