NDLI: Comparing Queues and Stacks As Machines for Laying Out Graphs

Please wait, while we are loading the content...

Comparing Queues and Stacks As Machines for Laying Out Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Rosenberg, Arnold L. Heath, Lenwood S. Leighton, Frank Thomson
Copyright Year	1992
Abstract	The relative powers of queues and stacks are compared as mechanisms for laying out the edges of a graph. In a k-queue layout, vertices of the graph are placed in some linear order (also called a linear arrangement), and each edge is assigned to exactly one of the k queues, so that the edges assigned to each queue obey a first-in/first-out (FIFO) discipline. As the vertices are scanned left to right, an edge is enqueued on its assigned queue when its left endpoint is encountered and is dequeued from its queue when its right endpoint is encountered. In a k-stack layout, vertices of the graph are placed in some linear order, and each edge is assigned to exactly one of the k stacks so that the edges assigned to each stack obey a last-in/first-out discipline. As the vertices are scanned left to right, an edge is pushed on its assigned stack when its left endpoint is encountered and is popped from its stack when its right endpoint is encountered. The paper has three main results. First, a tradeoff between queuenumber and stacknumber is shown for a fixed linear order of the vertices of G. In particular, for a fixed-order layout of a graph G, \[ {\text{queuenumber }} \times {\text{ stacknumber }} \geq {\text{ cutwidth/valence }}( G ).\] Second, it is shown that every 1-queue graph has a 2-stack layout and that every 1-stack graph has a 2-queue layout. Third, in a surprising display of the power of queues, it is shown that the ternary hypercube requires exponentially more stacks than queues. More precisely, an N-vertex ternary hypercube has a $( 2\log _3 N )$-queue layout but requires $\Omega ( N^{1/9 - \epsilon } )$ stacks, $\epsilon > 0$, in any stack layout. Also, some asymptotic bounds for the queuenumber of bounded-valence graphs are derived.
Starting Page	398
Ending Page	412
Page Count	15
File Format	PDF
ISSN	08954801
DOI	10.1137/0405031
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	5
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-08
Access Restriction	Subscribed
Subject Keyword	queue layout Applications of graph theory graph embedding Graph theory stack layout book embedding ternary hypercube
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Laying Out Graphs Using Queues

Stack and Queue Layouts of Directed Acyclic Graphs: Part I

Stack and Queue Layouts of Posets

Stack and Queue Layouts of Directed Acyclic Graphs: Part II

Stacks, Queues and Tracks: Layouts of Graph Subdivisions

Stacks, Queues and Tracks: Layouts of Graph Subdivisions

On Linear Layouts of Graphs

Queue Layouts of Hypercubes

On Linear Layouts of Graphs

Comparing Queues and Stacks As Machines for Laying Out Graphs

Similar Documents

Laying Out Graphs Using Queues

Stack and Queue Layouts of Directed Acyclic Graphs: Part I

Stack and Queue Layouts of Posets

Stack and Queue Layouts of Directed Acyclic Graphs: Part II

Stacks, Queues and Tracks: Layouts of Graph Subdivisions

Stacks, Queues and Tracks: Layouts of Graph Subdivisions

On Linear Layouts of Graphs

Queue Layouts of Hypercubes

On Linear Layouts of Graphs

Comparing Queues and Stacks As Machines for Laying Out Graphs