arXiv:2508.17349 · v2

2-Layer Fan-Planarity in Polynomial Time

首次提交 2025-08-24 21:06

版本更新 2026-11-12 17:06

雷达观测 2026-11-13 14:15

摘要

In this paper, we give a polynomial-time algorithm for deciding whether a bipartite graph admits a 2-layer fan-planar drawing. This resolves an open problem posed in several papers since 2015. We also obtain a linear-time algorithm for the one-sided case.

作者备注：A preliminary version appeared in the proceedings of GD 2026