KIT | KIT-Bibliothek | Impressum | Datenschutz

An SPQR-tree-like embedding representation for level planarity

Brückner, Guido 1; Rutter, I.
1 Karlsruher Institut für Technologie (KIT)


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.

Verlagsausgabe §
DOI: 10.5445/IR/1000130624
Veröffentlicht am 18.03.2021
DOI: 10.4230/LIPIcs.ISAAC.2020.8
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2020
Sprache Englisch
Identifikator ISBN: 978-3-9597717-3-3
ISSN: 1868-8969
KITopen-ID: 1000130624
Erschienen in 31st International Symposium on Algorithms and Computation (ISAAC 2020). Ed.: Y. Cao
Veranstaltung 31st International Symposium on Algorithms and Computation (ISAAC 2020), Online, 14.12.2020 – 18.12.2020
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten 81-815
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 181
Schlagwörter SPQR-tree, Level planarity, Partial drawings, Simultaneous drawings
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page