The Rique-Number of Graphs

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

The Rique-Number of Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The Rique-Number of Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

Počet stran výsledku

15

Strana od-do

371-386

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Tokyo

Datum konání akce

13. 9. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—