Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016)
DOI: 10.7155/jgaa.00417
On Aligned Bar 1Visibility Graphs
Franz J. Brandenburg,
Alexander Esch, and
Daniel Neuwirth
Vol. 21, no. 3, pp. 281312, 2017. Regular paper.
Abstract A graph is called a bar 1visibility 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 1visibility 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 $4n10$
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 pathaddition, that
admits the addition of vertexdisjoint paths to a given graph and
show that $AB1V$ graphs are closed under pathaddition. This
distinguishes $AB1V$ graphs from other classes of graphs. In
particular, we explore the relationship to other classes of
beyondplanar graphs and show that every outer 1planar graph is an
$AB1V$ graph, whereas $AB1V$ graphs are incomparable, e.g., to planar,
kplanar, outer fanplanar, outer fancrossing free, fancrossing
free, bar $(1,j)$visibility, and RAC graphs.

Submitted: May 2016.
Reviewed: November 2016.
Revised: December 2016.
Reviewed: December 2016.
Revised: December 2016.
Accepted: January 2017.
Final: January 2017.
Published: February 2017.

Journal Supporters
