TY - GEN

T1 - The Rique-Number of Graphs

AU - Bekos, Michael A.

AU - Felsner, Stefan

AU - Kindermann, Philipp

AU - Kobourov, Stephen

AU - Kratochvíl, Jan

AU - Rutter, Ignaz

N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - Linear layout

KW - Restricted-input queue

KW - Rique-number

UR - http://www.scopus.com/inward/record.url?scp=85148696239&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85148696239&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-22203-0_27

DO - 10.1007/978-3-031-22203-0_27

M3 - Conference contribution

AN - SCOPUS:85148696239

SN - 9783031222023

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 371

EP - 386

BT - Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers

A2 - Angelini, Patrizio

A2 - von Hanxleden, Reinhard

PB - Springer Science and Business Media Deutschland GmbH

T2 - 30th International Symposium on Graph Drawing and Network Visualization, GD 2022

Y2 - 13 September 2022 through 16 September 2022

ER -