Result: Queue layouts of iterated line directed graphs

Title:
Queue layouts of iterated line directed graphs
Authors:
HASUNUMA, Toru
Source:
Advances in graph drawing; The 11th International Symposium on Graph DrawingDiscrete applied mathematics. 155(9):1141-1154
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 23 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Assignation, Assignment, Asignación, Borne inférieure, Lower bound, Cota inferior, Borne supérieure, Upper bound, Cota superior, Calcul 3 dimensions, Three-dimensional calculations, Combinatoire, Combinatorics, Combinatoria, Digraphe, Digraph, Digrafo, Etirage, Drawing, Estiramiento, File attente, Queue, Fila espera, Graphe ligne, Line graph, Grafo línea, Graphe linéaire, Linear graph, Grafo lineal, Graphe orienté, Directed graph, Grafo orientado, Implantation (topométrie), Layout, Implantación (topometría), Informatique théorique, Computer theory, Informática teórica, Itération, Iteration, Iteracción, Optimisation, Optimization, Optimización, Relation ordre, Ordering, Relación orden, Réseau interconnexion, Interconnection network, Red interconexión, 05C20, Graphe de Bruijn, Butterfly directed graphs, Interconnection networks, Iterated line directed graphs, Kautz directed graphs, Queue layout, Three-dimensional drawing, de Bruijn directed graphs
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Mathematical and Natural Sciences, The University of Tokushima, 1-1 Minamijosanjima, Tokushima 770-8502, Japan
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18788147
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.18788147
Database:
PASCAL Archive

Further Information

In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph. We present upper and lower bounds on the queuenumber of an iterated line directed graph Lk(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k. Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of Lk(G), it is shown that for any fixed directed graph G, Lk(G) has a three-dimensional drawing with O(n) volume, where n is the number of vertices in Lk(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.