Outside-Obstacle Representations with All Vertices on the Outer Face
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910831909797888 |
|---|---|
| author | Firman, Oksana Kindermann, Philipp Klawitter, Jonathan Klemz, Boris Klesen, Felix Wolff, Alexander |
| author_facet | Firman, Oksana Kindermann, Philipp Klawitter, Jonathan Klemz, Boris Klesen, Felix Wolff, Alexander |
| contents | An obstacle representation of a graph $G$ consists of a set of polygonal obstacles and a drawing of $G$ as a visibility graph with respect to the obstacles: vertices are mapped to points and edges to straight-line segments such that each edge avoids all obstacles whereas each non-edge intersects at least one obstacle. Obstacle representations have been investigated quite intensely over the last few years. Here we focus on outside-obstacle representations (OORs) that use only one obstacle in the outer face of the drawing. It is known that every outerplanar graph admits such a representation.
We strengthen this result by showing that every (partial) 2-tree has an OOR. We also consider restricted versions of OORs where the vertices of the graph form a convex polygon or even a regular polygon. We characterize when the complement of a tree and when a complete graph minus a simple cycle admits a convex OOR. We construct regular OORs for all (partial) outerpaths, cactus graphs, and grids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_13015 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Outside-Obstacle Representations with All Vertices on the Outer Face Firman, Oksana Kindermann, Philipp Klawitter, Jonathan Klemz, Boris Klesen, Felix Wolff, Alexander Computational Geometry 68R10, 05C62 An obstacle representation of a graph $G$ consists of a set of polygonal obstacles and a drawing of $G$ as a visibility graph with respect to the obstacles: vertices are mapped to points and edges to straight-line segments such that each edge avoids all obstacles whereas each non-edge intersects at least one obstacle. Obstacle representations have been investigated quite intensely over the last few years. Here we focus on outside-obstacle representations (OORs) that use only one obstacle in the outer face of the drawing. It is known that every outerplanar graph admits such a representation. We strengthen this result by showing that every (partial) 2-tree has an OOR. We also consider restricted versions of OORs where the vertices of the graph form a convex polygon or even a regular polygon. We characterize when the complement of a tree and when a complete graph minus a simple cycle admits a convex OOR. We construct regular OORs for all (partial) outerpaths, cactus graphs, and grids. |
| title | Outside-Obstacle Representations with All Vertices on the Outer Face |
| topic | Computational Geometry 68R10, 05C62 |
| url | https://arxiv.org/abs/2202.13015 |