Problems

The following constrained planarity problems are listed on this website:

\(\langle \alpha, \beta, \gamma \rangle\)-drawings
(Angelini et al. 2015)

\(\mathcal T\)-level Planarity
\(\mathcal T\)-level Planarity is NP-complete for instances…

(Embedded) Strip Planarity
(Embedded) Strip Planarity can be solved in time…

(Embedded) Upward Planarity
(Embedded) Upward Planarity can be solved in time…

(Standard) Planarity
A graph is planar if it can be embedded in the plane such that no two edges cross.

Book?
Book? is NP-complete for instances…

Clustered Level Planarity
Clustered Level Planarity is NP-complete for instances…

Clustered Planarity
A graph is cluster planar if there is a planar drawing of it where we can also add its clusters as closed regions that only cross the edges that leave the respective cluster.

Connected SEFE-2
Connected SEFE-2 can be solved in time…

Hierarchical Planarity
SEFE is NP-complete for instances…

Level Planarity
A graph is level planar if it can be embedded in the plane such that no two edges cross and the vertices lie on some prescribed horizontal lines.

MaxSEFE
MaxSEFE is NP-complete for instances…

NodeTrix Planarity
Row-Column-Independent NodeTrix Planarity can be solved in time…

Outer Planarity
A graph is outerplanar if it can be embedded in the plane such that no two edges cross and all vertices are incident to the same face, which we chose to be the outer one.

Partial Planarity
Partial Planarity can be solved in time…

Partial Rotation Planarity
Partial Rotation Planarity can be solved in time…

Partial Rotation Planarity with flips
Partial Rotation Planarity with flips can be solved in time…

Partially Embedded Planarity
In…

Partially PQ-constrained Planarity
Partially PQ-constrained Planarity can be solved in time…

Partitioned \(\mathcal T\)-coherent 2-page Book Embedding
Partitioned \(\mathcal T\)-coherent 2-page Book Embedding can be solved in time…

Partitioned \(\mathcal T\)-coherent 3-page Book Embedding
Partitioned \(\mathcal T\)-coherent 3-page Book Embedding is NP-complete for instances…

Partitioned 2-page Book Embedding
Partitioned 2-page Book Embedding can be solved in time…

Partitioned 3-Page Book Embedding
Partitioned 3-Page Book Embedding is NP-complete for instances…

Proper \(\mathcal T\)-level Planarity
Proper \(\mathcal T\)-level Planarity can be solved in time…

Proper Clustered Level Planarity
Proper Clustered Level Planarity can be solved in time…

Radial Level Planarity
Radial Level Planarity is a generalization of Level Planarity where levels are not represented by axis-parallel lines, but by concentric…

Row-Column-Independent NodeTrix Planarity
Row-Column-Independent NodeTrix Planarity can be solved in time…

SEFE-2
Simultaneous Embedding with Fixed Edges is NP-complete for instances…

SEFE-3
SEFE-3 is NP-complete for instances…

Simultaneous Embedding with Fixed Edges
SEFE is NP-complete for instances…

Streamed Backbone Planarity
Streamed Backbone Planarity is NP-complete for instances…

Streamed Planarity
Streamed Planarity is NP-complete for instances…

Strip Planarity
Strip Planarity can be solved in time…

Synchronized Planarity
Synchronized Planarity can be solved in time…

Upward Planarity
Upward Planarity is NP-complete for instances…

Weak Realizability
Weak Realizability is NP-complete for instances…

ec-Planarity
ec-Planarity can be solved in time…

ec-Planarity with free edges
ec-Planarity with free edges can be solved in time…
No matching items