The Rique-Number of Graphs

Michael A. Bekos, Stefan Felsner, Philipp Kindermann, Stephen Kobourov, Jan Kratochvíl, Ignaz Rutter

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We continue the study of linear layouts of graphs in relation to known data structures. At a high level, given a data structure, the goal is to find a linear order of the vertices of the graph and a partition of its edges into pages, such that the edges in each page follow the restriction of the given data structure in the underlying order. In this regard, the most notable representatives are the stack and queue layouts, while there exists some work also for deques. In this paper, we study linear layouts of graphs that follow the restriction of a restricted-input queue (rique), in which insertions occur only at the head, and removals occur both at the head and the tail. We characterize the graphs admitting rique layouts with a single page and we use the characterization to derive a corresponding testing algorithm when the input graph is maximal planar. We finally give bounds on the number of needed pages (so-called rique-number) of complete graphs.

Original languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
EditorsPatrizio Angelini, Reinhard von Hanxleden
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages16
ISBN (Print)9783031222023
StatePublished - 2023
Event30th International Symposium on Graph Drawing and Network Visualization, GD 2022 - Tokyo, Japan
Duration: Sep 13 2022Sep 16 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13764 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference30th International Symposium on Graph Drawing and Network Visualization, GD 2022


  • Linear layout
  • Restricted-input queue
  • Rique-number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'The Rique-Number of Graphs'. Together they form a unique fingerprint.

Cite this