2-Layer Fan-Planarity in Polynomial Time
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "2-Layer Fan-Planarity in Polynomial Time".
Jane: Here's the gist of the paper. 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 Theorem 1.
Tom: There is a polynomial-time algorithm that, given a bipartite graph G, decides whether G admits a 2-layer fan-planar drawing Our algorithm employs a different idea from those used in existing algorithms Problem Definition and Goal A 2-layer drawing of a bipartite graph G = (X ∪ Y, E) is defined as a drawing where the vertices in X and Y are drawn on two horizontal lines, respectively, and each edge is drawn as a straight line segment between these two parallel lines A 2-layer drawing is said to be fan-planar if for every edge e, the crossing edges with e have a common end vertex; these edges form a “fan” A bipartite graph admitting a 2-layer fan-planar drawing is called a 2-layer fan-planar graph The problem of determining whether an input graph admits a fan-planar drawing is known to be NP-complete Degree Reduction Rules The paper presents several reduction rules aimed at reducing the maximum degree of a graph to a constant while preserving its 2-layer fan-planarity 1.
Jane: Lemma 1 states that if a vertex v has degree-1 neighbors u, w in N(v), then G has a 2-layer fan-planar drawing if and only if G − w does 2.
Tom: Lemma 2 shows that if a vertex v has at least five neighbors of degree at least 3, then G has no 2-layer fan-planar drawing 3.
Paper summary: Jane: So, wrapping up this discussion on "2Layer FanPlanarity in Polynomial Time," the authors have essentially provided a polynomial-time algorithm for deciding if a bipartite graph admits this specific two-layer drawing style <ref:2508.17349#pg1,a polynomial-time algorithm for deciding>.
Tom: It’s important to remember that they did this by employing a different idea than what was used in some existing algorithms, which suggests their approach might be computationally distinct and potentially faster or more robust.
Lu: The title itself points to the key contribution: achieving this decision problem in polynomial time for two-layer fan-planar graphs <ref:2508.17349#pg1>.
Meng: For us in production, the real impact is that we can now build tools to validate if a graph layout meets these specific criteria efficiently, which is something that was previously out of reach.
Jane: What this means simply is that we have a concrete, efficient way to check for this specific geometric arrangement in bipartite graphs without having to explore every possible drawing configuration.
Tom: It resolves the open problem from several years ago by giving us a practical tool, so anyone interested in these graph properties can now use this algorithm.
Lu: The authors' work provides a framework built on reduction rules and structural analysis that allows for this efficient decision process, which is a solid foundation for future research into related drawing problems.
Meng: I’m still thinking about the scale; if we had a graph with millions of vertices, having a polynomial time algorithm is good, but does it mean it’s fast enough when the constants in that polynomial are huge?
Jane: That's a fair concern about real-world deployment, and while they didn't detail those scaling factors in this summary, the paper shows they focused on reducing the maximum degree to a constant using those lemmas.
Tom: That reduction is what gives us confidence that we can control the complexity based on local vertex properties rather than just the total size of the graph.
Lu: Ultimately, this work moves us from knowing a problem is hard to having an efficient way to solve it, which opens up avenues for applying these structural constraints in other areas of graph representation.
Conclusion: Tom: So, this paper is about finding a way to decide if a bipartite graph can have that specific two-layer drawing style in polynomial time.
Jane: Right, so we know this was an open problem since fifteen years ago, and now they’ve found a method to check it efficiently.
Tom: The authors are basically showing us an algorithm that doesn't just guess; it uses some different structural rules to figure out the answer quickly.
Lu: It looks like their method focuses on reducing the maximum degree of the graph down to just a constant number, which makes it manageable for computation.
Meng: A constant maximum degree is good because it means we can control how hard the calculation gets based on a simple limit, not just how big the whole graph is.
Lalam: It seems they've defined several specific reduction rules—like if a vertex has certain neighbors, or if it has many degree-two neighbors—to prove whether that drawing style is possible or not.
Jane: So for someone listening who doesn't read math, this means we can now take a bipartite graph and use this tool to know right away if it’s worth trying to draw it in that specific two-layer fan-planar way.
Tom: It resolves the NP-complete issue by giving us a polynomial time solution, which is a big deal because before this, figuring out if something exists was basically impossible for large graphs.
Lu: What this actually changes is that we can start using these structural constraints to design layouts for real applications instead of just theoretical ones.
Meng: I wonder how fast the actual algorithm runs on a graph that's actually used in production; we need to know if it’s fast enough when things get big.
Jane: That’s a fair point, and it leads us right into what the authors are saying about their specific approach versus other methods out there.
Hokkaido University · Nagoya University
cs.CG, cs.DS
Submitted: 2025-08-24
Updated: 2026-11-12
Comments: A preliminary version appeared in the proceedings of GD 2026
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 77/100
The gist: In this paper, we give a polynomial-time algorithm for deciding whether an input bipartite graph admits a 2-layer fan-planar drawing…
Key concepts
- 2-layer drawing
- A drawing where vertices from two sets, X and Y, are placed on two horizontal lines. Edges connect these lines as straight segments. This setup is the basic structure required before checking the fan-planarity condition.
- Fan-planar
- A 2-layer drawing is fan-planar if every edge has a property regarding its crossing edges: those edges that cross it must share a common endpoint with that edge. This creates a 'fan' structure for the crossings, which is the defining characteristic of the desired embedding.
- Bipartite graph
- A graph whose vertices can be divided into two disjoint sets, X and Y, such that every edge connects a vertex in X to one in Y. The problem specifically deals with determining if this type of structure allows for a 2-layer fan-planar drawing.
- Degree Reduction Rules
- These are specific logical rules (Lemmas 1 through 4) used within the algorithm. They help simplify the graph by reducing the maximum degree while ensuring that if these conditions hold, the original graph still possesses a 2-layer fan-planar drawing or lacks one.
Terminology
Summary
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 Theorem 1. p. 0 There is a polynomial-time algorithm that, given a bipartite graph G, decides whether G admits a 2-layer fan-planar drawing Our algorithm employs a different idea from those used in existing algorithms
Problem Definition and Goal
A 2-layer drawing of a bipartite graph G = (X ∪ Y, E) is defined as a drawing where the vertices in X and Y are drawn on two horizontal lines, respectively, and each edge is drawn as a straight line segment between these two parallel lines A 2-layer drawing is said to be fan-planar if for every edge e, the crossing edges with e have a common end vertex; these edges form a “fan” A bipartite graph admitting a 2-layer fan-planar drawing is called a 2-layer fan-planar graph The problem of determining whether an input graph admits a fan-planar drawing is known to be NP-complete
Degree Reduction Rules
The paper presents several reduction rules aimed at reducing the maximum degree of a graph to a constant while preserving its 2-layer fan-planarity
-
Lemma 1 states that if a vertex v has degree-1 neighbors u, w in N(v), then G has a 2-layer fan-planar drawing if and only if G − w does
-
Lemma 2 shows that if a vertex v has at least five neighbors of degree at least 3, then G has no 2-layer fan-planar drawing
-
Lemma 3 states that if a vertex v has at least five degree-2 neighbors u1,. p. 1.., u5 such that G − v has a matching saturating these neighbors, then G has no 2-layer fan-planar drawing
-
Lemma 4 establishes a condition for reduction: if a vertex v has three degree-2 neighbors u1,. p. 3..
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved recognition of 2-layer fan-planar graphs by providing a polynomial-time algorithm that exploits a recent polynomial-time algorithm for recognizing 2-layer k-planar graphs with fixed k [9]. This allows AI systems to efficiently decide whether an input bipartite graph admits a 2-layer fan-planar drawing.
-
Enhanced efficiency in checking fan-planarity through the use of reduction rules, such as Lemma 1 and Lemma 4, which aim to
reduce the maximum degree of a graph to a constant while preserving its 2-layer fan-planarity.
This enables the system to apply dynamic programming on bounded-degree graphs. -
Polynomial time complexity for deciding whether a bipartite graph admits a 2-layer fan-planar drawing is achieved by combining Lemma 5 (which bounds the maximum degree of reduced graphs) and Lemma 8 (which provides a fast algorithm for fixed k). This means AI systems can solve this problem in polynomial time, resolving an open problem since 2015.
-
Application of a dynamic programming algorithm on subgraphs induced by consecutive vertices, defined as draw(S, D, χ, C), allows the system to search for a fan-planar drawing among 2-layer k-planar drawings. This recurrence relation is modified to incorporate the fan-planarity requirement via Lemma 6.
-
The system can determine if a graph admits a 2-layer k-planar drawing that is also fan-planar by evaluating the recurrence of Lemma 6, where the running time bound is obtained in a similar manner as for k-planar drawings.
Sources
Related papers
- The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly
- k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
- Covering Points with Rectangular Boundaries
- Tiling 3D Space by (Translates of) a Single Polycube is Undecidable
- Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus
- Minimum central circles: chain order, seam obstructions, and exact finite certification