2-Layer Fan-Planarity in Polynomial Time

2025/08/24 by Kobayashi, Yasuaki, Okada, Yuto
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2508.17349

Abstract

In this paper, we give a polynomial-time algorithm for deciding whether an input bipartite graph admits a 2-layer fan-planar drawing, resolving an open problem posed in several papers since 2015.

Citations

• Pathwidth of 2-Layer k-Planar Graphs
• Recognizing 2-Layer and Outer k-Planar Graphs
• 2-Layer Graph Drawings with Bounded Pathwidth
• 2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
• 2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth
• On Layered Fan-Planar Graph Drawings
• A faster fixed parameter algorithm for two-layer crossing minimization
• The Density of Fan-Planar Graphs
• Methods for Visual Understanding of Hierarchical System Structures

Cited by

• Pathwidth of 2-Layer k-Planar Graphs

Related

• On Layered Fan-Planar Graph Drawings
• Simplifying Non-Simple Fan-Planar Drawings
• The thickness of fan-planar graphs is at most three
• Weakly and Strongly Fan-Planar Graphs
• On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs