Geodesic
On k-visibility graphs
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 345-360.

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

We examine several types of visibility graphs in which sightlines can pass through k objects. For k ≥ 1 we bound the maximum thickness of semi-bar k-visibility graphs between ⎡2/3(k + 1) ⎤ and 2k. In addition we show that the maximum number of edges in arc and circle k-visibility graphs on n vertices is at most (k+1)(3n−k−2) for n > 4k+4 and (n 2) for n ≤ 4k+4, while the maximum chromatic number is at most 6k+6. In semi-arc k-visibility graphs on n vertices, we show that the maximum number of edges is (n 2) for n ≤ 3k+3 and at most (k+1)(2n−(k+2)/2) for n > 3k+3, while the maximum chromatic number is at most 4k+4.
DOI : 10.7155/jgaa.00362
Keywords: bar visibility graphs, k-visibility graphs, graph thickness, chromatic number 
@article{JGAA_2015_19_1_a16,
     author = {Matthew Babbitt and Jesse Geneson and Tanya Khovanova},
     title = {On k-visibility graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {345--360},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00362},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00362/}
}
TY  - JOUR
AU  - Matthew Babbitt
AU  - Jesse Geneson
AU  - Tanya Khovanova
TI  - On k-visibility graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 345
EP  - 360
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00362/
DO  - 10.7155/jgaa.00362
LA  - en
ID  - JGAA_2015_19_1_a16
ER  - 
%0 Journal Article
%A Matthew Babbitt
%A Jesse Geneson
%A Tanya Khovanova
%T On k-visibility graphs
%J Journal of Graph Algorithms and Applications
%D 2015
%P 345-360
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00362/
%R 10.7155/jgaa.00362
%G en
%F JGAA_2015_19_1_a16
Matthew Babbitt; Jesse Geneson; Tanya Khovanova. On k-visibility graphs. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 345-360. doi : 10.7155/jgaa.00362. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00362/

Cité par Sources :