The Rique-Number of Graphs

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

doi:10.1007/978-3-031-22203-0_27

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 proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
Editors	Patrizio Angelini, Reinhard von Hanxleden
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	371-386
Number of pages	16
ISBN (Print)	9783031222023
DOIs	https://doi.org/10.1007/978-3-031-22203-0_27
State	Published - 2023
Externally published	Yes
Event	30th International Symposium on Graph Drawing and Network Visualization, GD 2022 - Tokyo, Japan Duration: Sep 13 2022 → Sep 16 2022

Publication series

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

Conference

Conference	30th International Symposium on Graph Drawing and Network Visualization, GD 2022
Country/Territory	Japan
City	Tokyo
Period	9/13/22 → 9/16/22

Keywords

Linear layout
Restricted-input queue
Rique-number

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Bekos, M. A., Felsner, S., Kindermann, P., Kobourov, S., Kratochvíl, J., & Rutter, I. (2023). The Rique-Number of Graphs. In P. Angelini, & R. von Hanxleden (Eds.), Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers (pp. 371-386). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13764 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-22203-0_27

The Rique-Number of Graphs. / Bekos, Michael A.; Felsner, Stefan; Kindermann, Philipp et al.
Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. ed. / Patrizio Angelini; Reinhard von Hanxleden. Springer Science and Business Media Deutschland GmbH, 2023. p. 371-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13764 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bekos, MA, Felsner, S, Kindermann, P, Kobourov, S, Kratochvíl, J & Rutter, I 2023, The Rique-Number of Graphs. in P Angelini & R von Hanxleden (eds), Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13764 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 371-386, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, Tokyo, Japan, 9/13/22. https://doi.org/10.1007/978-3-031-22203-0_27

Bekos MA, Felsner S, Kindermann P, Kobourov S, Kratochvíl J, Rutter I. The Rique-Number of Graphs. In Angelini P, von Hanxleden R, editors, Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2023. p. 371-386. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-22203-0_27

Bekos, Michael A. ; Felsner, Stefan ; Kindermann, Philipp et al. / The Rique-Number of Graphs. Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. editor / Patrizio Angelini ; Reinhard von Hanxleden. Springer Science and Business Media Deutschland GmbH, 2023. pp. 371-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d03665ea593c4fa48f07647e6b92a204,

title = "The Rique-Number of Graphs",

abstract = "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.",

keywords = "Linear layout, Restricted-input queue, Rique-number",

author = "Bekos, {Michael A.} and Stefan Felsner and Philipp Kindermann and Stephen Kobourov and Jan Kratochv{\'i}l and Ignaz Rutter",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 30th International Symposium on Graph Drawing and Network Visualization, GD 2022 ; Conference date: 13-09-2022 Through 16-09-2022",

year = "2023",

doi = "10.1007/978-3-031-22203-0_27",

language = "English (US)",

isbn = "9783031222023",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "371--386",

editor = "Patrizio Angelini and {von Hanxleden}, Reinhard",

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

address = "Germany",

}

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

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 -