On the Recognition of Outerplanar Graphs with Queue Number 1
2026-07-27 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study a way to arrange graph vertices in a line and group edges so that no edges cross or nest on the same page. They focus on graphs that require only one page for both stack and queue layouts, which for stacks are known to be outerplanar graphs. They found that checking if an outerplanar graph has a queue number of 1 is generally hard (NP-hard), but for a special type called maximal outerplanar graphs, it can be done quickly. They also explore how certain outerpaths relate to their vertex degree under these conditions.
graph theorylinear layoutstack layoutqueue layoutstack numberqueue numberouterplanar graphmaximal outerplanar graphNP-hardvertex degree
Authors
Michael A. Bekos, Thomas Depian, Stefan Felsner, Michael Kaufmann, Philipp Kindermann, Fabrizio Montecchiani, Maria Eleni Pavlidi, Alexandra Weinberger, Alexander Wolff, Johannes Zink
Abstract
A linear layout of a graph is defined as a total order of the vertices and a partition of the edges to pages. In a stack (queue) layout, no two edges on the same page may cross (nest). The stack (queue) number of a graph is the minimum number of pages required in a stack (queue) layout. This paper focuses on characterizing and recognizing graphs that have both stack number 1 and queue number 1. It is known that the graphs with stack number 1 are exactly the outerplanar graphs. We show that (i) deciding whether a given outerplanar graph has queue number 1 is NP-hard; (ii) deciding whether a given maximal outerplanar graph has queue number 1 can be done in linear time. Moreover, we investigate the interplay between outerpaths with queue number 1 and their maximum vertex degree.