KIT | KIT-Bibliothek | Impressum | Datenschutz

On Mixed Linear Layouts of Series-Parallel Graphs

Angelini, P.; Bekos, M. A.; Kindermann, P.; Mchedlidze, Tamara

A mixed s-stack q-queue layout of a graph consists of a linear order of its vertices and of a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. Recently, Pupyrev disproved this conjectured by demonstrating a planar partial 3-tree that does not admit a 1-stack 1-queue layout. In this note, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees, also known as series-parallel graphs.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2020
Sprache Englisch
Identifikator KITopen-ID: 1000131340
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page