![]() |
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.
![]() |
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
|