The Rique-Number of Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455449" target="_blank" >RIV/00216208:11320/22:10455449 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-031-22203-0_27" target="_blank" >https://doi.org/10.1007/978-3-031-22203-0_27</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-22203-0_27" target="_blank" >10.1007/978-3-031-22203-0_27</a>
Alternative languages
Result language
angličtina
Original language name
The Rique-Number of Graphs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Graph Drawing and Network Visualization 30th International Symposium, GD 2022, Tokyo, Japan, September 13–16, 2022, Revised Selected Papers
ISBN
978-3-031-22202-3
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
15
Pages from-to
371-386
Publisher name
Springer
Place of publication
Cham
Event location
Tokyo
Event date
Sep 13, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—