Geodesic
Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 519-552.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00606
Keywords: intersection graphs, paths on a grid, outerplanar graphs, cacti 
@article{JGAA_2022_26_4_a5,
     author = {Eranda \c{C}ela and Elisabeth Gaar},
     title = {Monotonic {Representations} of {Outerplanar} {Graphs} as {Edge} {Intersection} {Graphs} of {Paths} on a {Grid}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {519--552},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2022},
     doi = {10.7155/jgaa.00606},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00606/}
}
TY  - JOUR
AU  - Eranda Çela
AU  - Elisabeth Gaar
TI  - Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 519
EP  - 552
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00606/
DO  - 10.7155/jgaa.00606
LA  - en
ID  - JGAA_2022_26_4_a5
ER  - 
%0 Journal Article
%A Eranda Çela
%A Elisabeth Gaar
%T Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid
%J Journal of Graph Algorithms and Applications
%D 2022
%P 519-552
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00606/
%R 10.7155/jgaa.00606
%G en
%F JGAA_2022_26_4_a5
Eranda Çela; Elisabeth Gaar. Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 4, pp. 519-552. doi : 10.7155/jgaa.00606. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00606/

Cité par Sources :