Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00606
Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
Vol. 26, no. 4, pp. 519-552, 2022. Regular paper.
Abstract In a representation of a graph $G$ as an edge intersection graph of paths on a
grid (EPG) every vertex of $G$ is represented by a path on a grid and two
paths share a grid edge iff the corresponding vertices are
adjacent.
In a monotonic EPG
representation every path on the grid is
ascending in both rows and columns. In a (monotonic) $B_k$-EPG
representation every path on the grid has at most $k$ bends.
The (monotonic) bend number $b(G)$ ($b^m(G)$) of a graph
$G$
is the smallest natural number $k$ for which there exists a (monotonic)
$B_k$-EPG representation of $G$.
In this paper we deal with the monotonic bend number of outerplanar graphs and show
that $b^m(G)\leqslant 2$ holds for every outerplanar graph $G$.
Moreover, we characterize the maximal outerplanar graphs and the cacti
with (monotonic) bend number equal to $0$, $1$ and $2$
in terms of forbidden induced subgraphs.
As a byproduct we obtain low-degree polynomial time algorithms to
construct (monotonic) EPG
representations with the smallest possible number of bends for
maximal outerplanar graphs and cacti.
This work is licensed under the terms of the CC-BY license.
|
Submitted: March 2022.
Reviewed: August 2022.
Revised: September 2022.
Accepted: September 2022.
Final: September 2022.
Published: December 2022.
Communicated by
William S. Evans
|
Journal Supporters
|