On Aligned Bar 1-Visibility Graphs

Abstract

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.