Abstract
n 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) Bk-EPG representation every path on the grid has at most k bends. The (monotonic) bend number b(G) (bm(G)) of a graph G is the smallest natural number k for which there exists a (monotonic) Bk-EPG representation of G.
In this paper we deal with the monotonic bend number of outerplanar graphs and show that bm(G)⩽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.
In this paper we deal with the monotonic bend number of outerplanar graphs and show that bm(G)⩽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.
| Original language | English |
|---|---|
| Number of pages | 58 |
| Publication status | Published - 6 Aug 2019 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
Fields of Expertise
- Information, Communication & Computing
Treatment code (Nähere Zuordnung)
- Basic - Fundamental (Grundlagenforschung)