Strip Planarity Testing

Angelini, Patrizio and Da Lozzo, Giordano and Di Battista, Giuseppe and Frati, Fabrizio (2013) Strip Planarity Testing. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 37-48(Official URL:

Full text not available from this repository.


In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph G(V,E) and a function γ:V → {1,2,…,k} and asks whether a planar drawing of G exists such that each edge is monotone in the y-direction and, for any u,v ∈ V with γ(u) < γ(v), it holds y(u) < y(v). The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity, upward planarity, and level planarity. We show that the problem is polynomial-time solvable if G has a fixed planar embedding.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.180 Cluster
P Styles > P.480 Layered
P Styles > P.840 Upward

Actions (login required)

View Item View Item