Geodesic
On Linear Layouts of Graphs
Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 2.

Voir la notice de l'article provenant de la source Episciences

In a total order of the vertices of a graph, two edges with no endpoint in common can be \emphcrossing, \emphnested, or \emphdisjoint. A \emphk-stack (respectively, \emphk-queue, \emphk-arch) \emphlayout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (non-nested, non-disjoint) edges. Motivated by numerous applications, stack layouts (also called \emphbook embeddings) and queue layouts are widely studied in the literature, while this is the first paper to investigate arch layouts.\par Our main result is a characterisation of k-arch graphs as the \emphalmost (k+1)-colourable graphs; that is, the graphs G with a set S of at most k vertices, such that G S is (k+1)-colourable.\par In addition, we survey the following fundamental questions regarding each type of layout, and in the case of queue layouts, provide simple proofs of a number of existing results. How does one partition the edges given a fixed ordering of the vertices? What is the maximum number of edges in each type of layout? What is the maximum chromatic number of a graph admitting each type of layout? What is the computational complexity of recognising the graphs that admit each type of layout?\par A comprehensive bibliography of all known references on these topics is included. \par 
@article{DMTCS_2004_6_2_a8,
     author = {Dujmovi\'c, Vida and Wood, David R.},
     title = {On {Linear} {Layouts} of {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {6},
     number = {2},
     year = {2003-2004},
     doi = {10.46298/dmtcs.317},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.317/}
}
TY  - JOUR
AU  - Dujmović, Vida
AU  - Wood, David R.
TI  - On Linear Layouts of Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2003-2004
VL  - 6
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.317/
DO  - 10.46298/dmtcs.317
LA  - en
ID  - DMTCS_2004_6_2_a8
ER  - 
%0 Journal Article
%A Dujmović, Vida
%A Wood, David R.
%T On Linear Layouts of Graphs
%J Discrete mathematics & theoretical computer science
%D 2003-2004
%V 6
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.317/
%R 10.46298/dmtcs.317
%G en
%F DMTCS_2004_6_2_a8
Dujmović, Vida; Wood, David R. On Linear Layouts of Graphs. Discrete mathematics & theoretical computer science, Tome 6 (2003-2004) no. 2. doi : 10.46298/dmtcs.317. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.317/

Cité par Sources :