Geodesic
On Aligned Bar 1-Visibility Graphs
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016) , Tome 21 (2017) no. 3, pp. 281-312.

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

A graph is called a bar 1-visibility graph if its vertices can be represented as horizontal segments, called bars, and each edge corresponds to a vertical line of sight which can traverse another bar. If all bars are aligned at one side, then the graph is an aligned bar 1-visibility graph, $AB1V$ graph for short. We consider $AB1V$ graphs from different angles. First, we study combinatorial properties and $K_5$ subgraphs. Then, we establish a difference between maximal and optimal $AB1V$ graphs, where optimal $AB1V$ graphs have the maximum of $4n-10$ edges. We show that optimal $AB1V$ graphs can be recognized in $\mathcal{O}(n^2)$ time and prove that an $AB1V$ representation is determined by an ordering of the bars either from left to right or by length. Finally, we introduce a new operation, called path-addition, that admits the addition of vertex-disjoint paths to a given graph and show that $AB1V$ graphs are closed under path-addition. This distinguishes $AB1V$ graphs from other classes of graphs. In particular, we explore the relationship to other classes of beyond-planar graphs and show that every outer 1-planar graph is an $AB1V$ graph, whereas $AB1V$ graphs are incomparable, e.g., to planar, k-planar, outer fan-planar, outer fan-crossing free, fan-crossing free, bar $(1,j)$-visibility, and RAC graphs. 
@article{JGAA_2017_21_3_a3,
     author = {Franz Brandenburg and Alexander Esch and Daniel Neuwirth},
     title = {On {Aligned} {Bar} {1-Visibility} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {281--312},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2017},
     doi = {10.7155/jgaa.00417},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00417/}
}
TY  - JOUR
AU  - Franz Brandenburg
AU  - Alexander Esch
AU  - Daniel Neuwirth
TI  - On Aligned Bar 1-Visibility Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 281
EP  - 312
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00417/
DO  - 10.7155/jgaa.00417
LA  - en
ID  - JGAA_2017_21_3_a3
ER  - 
%0 Journal Article
%A Franz Brandenburg
%A Alexander Esch
%A Daniel Neuwirth
%T On Aligned Bar 1-Visibility Graphs
%J Journal of Graph Algorithms and Applications
%D 2017
%P 281-312
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00417/
%R 10.7155/jgaa.00417
%G en
%F JGAA_2017_21_3_a3
Franz Brandenburg; Alexander Esch; Daniel Neuwirth. On Aligned Bar 1-Visibility Graphs. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation  (WALCOM 2016)
					, Tome 21 (2017) no. 3, pp. 281-312. doi : 10.7155/jgaa.00417. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00417/

Cité par Sources :