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 1-Visibility Graphs
Franz J. Brandenburg,
Alexander Esch, and
Daniel Neuwirth
Vol. 21, no. 3, pp. 281-312, 2017. Regular paper.
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.
|
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
|