2026-07-22T04:43:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13352 2024-03-06T10:51:46Z ddc:004 open_access

An SPQR-Tree-Like Embedding Representation for Level Planarity Brückner, Guido Rutter, Ignaz SPQR-tree Level planarity Partial drawings Simultaneous drawings An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algorithms, which seek a planar embedding of a graph subject to some given set of constraints. We develop an SPQR-tree-like data structure that represents all level-planar embeddings of a biconnected level graph with a single source, called the LP-tree, and give a simple algorithm to compute it in linear time. Moreover, we show that LP-trees can be used to adapt three constrained planarity algorithms to the level-planar case by using them as a drop-in replacement for SPQR-trees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guido Brückner and Ignaz Rutter 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.8 urn:nbn:de:0030-drops-133526 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode