KIT | KIT-Bibliothek | Impressum | Datenschutz

SPQR-tree-like embedding representation for level planarity

Brückner, Guido 1; Rutter, Ignaz
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

An SPQR-tree is a data structure that efficiently represents all planar embeddings of a connected 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 an 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 LP-trees as a drop-in replacement for SPQR-trees.


Verlagsausgabe §
DOI: 10.5445/IR/1000158502
Veröffentlicht am 05.05.2023
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2023
Sprache Englisch
Identifikator ISSN: 1920-180X
KITopen-ID: 1000158502
Erschienen in Journal of computational geometry
Verlag Computational Geometry Laboratory
Band 14
Heft 1
Seiten 48-77
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page