Advances in Graph Theory and Beyond Planarity

The field of graph theory is witnessing significant developments, with a focus on advancing our understanding of graph structures and their applications. Researchers are exploring new techniques to analyze and optimize graph parameters, such as treewidth, and to address long-standing conjectures. Notably, the study of $k$-planarity is gaining traction, with efforts to better comprehend the local crossing number and its relationship to other graph invariants. Furthermore, the connection between FO transductions and fan-crossing drawings is being investigated, which may lead to breakthroughs in our understanding of planar graphs and beyond. Some particularly noteworthy papers in this area include: The paper On the Complexity of Claw-Free Vertex Splitting, which settles an open problem and provides a cubic-order kernel for Claw-Free Vertex Splitting. The paper k-Planar and Fan-Crossing Drawings and Transductions of Planar Graphs, which introduces a two-way connection between FO transductions and fan-crossing drawings, with potential implications for the study of toroidal graphs.

Sources

On the Complexity of Claw-Free Vertex Splitting

Treewidth of Outer $k$-Planar Graphs

k-Planar and Fan-Crossing Drawings and Transductions of Planar Graphs

Straight-line Orthogonal Drawing of Complete Ternary Tree Requires $O(n^{1.032})$ Area

Contributions to conjectures in planar graphs: Induced Substructures, Treewidth, and Dominating Sets

Structural Parameterizations of $k$-Planarity

Built with on top of