In the constrained planarity setting, we ask whether a graph can be drawn such that no edges cross and that some given further constraints are satisfied. Click on one of the problem variants below to explore what these constraints may look like, or read more about this website on the About page.

G cluster_P P cluster_csefe2 cluster_ecfree cluster_X ? cluster_NPC NPC cluster_sefe radiallevel Radial Level Planarity clustered Clustered Planarity radiallevel->clustered stripemb (Embedded) Strip Planarity strip Strip Planarity stripemb->strip upwemb (Embedded) Upward Planarity stripemb->upwemb synchronized Synchronized Planarity clustered->synchronized abg ⟨α, β, γ⟩-drawings clustered->abg propertl Proper 𝒯-level Planarity parttcoh2page Partitioned 𝒯-coherent 2-page Book Embedding propertl->parttcoh2page tlevel 𝒯-level Planarity propertl->tlevel partrot Partial Rotation Planarity partiallyemb Partially Embedded Planarity partrot->partiallyemb partrotflip Partial Rotation Planarity with flips partrot->partrotflip part2page Partitioned 2-page Book Embedding part2page->parttcoh2page rcinodetrix Row- Column- Independent NodeTrix Planarity rcinodetrix->synchronized nodetrix NodeTrix Planarity rcinodetrix->nodetrix csefe2 Connected SEFE-2 csefe2->clustered csefe2->parttcoh2page part3page Partitioned 3-Page Book Embedding parttcoh2page->part3page partial Partial Planarity streamedbackbone Streamed Backbone Planarity partial->streamedbackbone ec ec- Planarity ec->partiallyemb ecfree ec- Planarity with free edges ec->ecfree strip->clustered sefe2 SEFE-2 synchronized->sefe2 level Level Planarity level->radiallevel level->strip propercl Proper Clustered Level Planarity level->propercl partiallyemb->clustered upward Upward Planarity upwemb->upward standard (Standard) Planarity standard->partrot standard->part2page standard->partial standard->ec standard->level outer Outer Planarity outer->standard ecfree->synchronized partpqcons Partially PQ- constrained Planarity ecfree->partpqcons partrotflip->ecfree propercl->propertl clusteredlevel Clustered Level Planarity propercl->clusteredlevel maxsefe MaxSEFE sefe2->maxsefe sefe3 SEFE-3 sefe2->sefe3 parttcoh3page Partitioned 𝒯-coherent 3-page Book Embedding parttcoh3page->streamedbackbone parttcoh3page->sefe3 book Book? sefe Simultaneous Embedding with Fixed Edges streamedbackbone->sefe clusteredlevel->sefe3 sefe3->sefe hierarchical Hierarchical Planarity upward->sefe part3page->parttcoh3page streamed Streamed Planarity streamed->streamedbackbone sefe->hierarchical weakrealizeab Weak Realizability sefe->weakrealizeab

This hierarchy was initially suggested by Schaefer (2013) and later extended by Da Lozzo (2015).

References

Da Lozzo, Giordano. 2015. “Planar Graphs with Vertices in Prescribed Regions:models, Algorithms, and Complexity.” PhD thesis, Roma Tre University. http://www.dia.uniroma3.it/~dalozzo/files/phd-thesis-giordano-dalozzo.pdf.
Schaefer, Marcus. 2013. “Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants.” Journal of Graph Algorithms and Applications 17 (4): 367–440. https://doi.org/10.7155/jgaa.00298.