Geodesic
Improved Bounds for Track Numbers of Planar Graphs
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 323-341.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A track layout of a graph consists of a vertex coloring and a total order of each color class, such that no two edges cross between any two color classes. The track number of a graph is the minimum number of colors required by a track layout of the graph. This paper improves lower and upper bounds on the track number of several families of planar graphs. We prove that every planar graph has track number at most $225$ and every planar $3$-tree has track number at most $25$. Then we show that there exist outerplanar graphs whose track number is $5$, which leads to the best known lower bound of $8$ for planar graphs. Finally, we investigate leveled planar graphs and tighten bounds on the track number of weakly leveled graphs, Halin graphs, and X-trees.
DOI : 10.7155/jgaa.00536
Keywords: track layout, track number, queue layout, planar graph 
@article{JGAA_2020_24_3_a9,
     author = {Sergey Pupyrev},
     title = {Improved {Bounds} for {Track} {Numbers} of {Planar} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {323--341},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2020},
     doi = {10.7155/jgaa.00536},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00536/}
}
TY  - JOUR
AU  - Sergey Pupyrev
TI  - Improved Bounds for Track Numbers of Planar Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 323
EP  - 341
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00536/
DO  - 10.7155/jgaa.00536
LA  - en
ID  - JGAA_2020_24_3_a9
ER  - 
%0 Journal Article
%A Sergey Pupyrev
%T Improved Bounds for Track Numbers of Planar Graphs
%J Journal of Graph Algorithms and Applications
%D 2020
%P 323-341
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00536/
%R 10.7155/jgaa.00536
%G en
%F JGAA_2020_24_3_a9
Sergey Pupyrev. Improved Bounds for Track Numbers of Planar Graphs. Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 323-341. doi : 10.7155/jgaa.00536. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00536/

Cité par Sources :