| Autor: |
Evans, William, Gethner, Ellen, Spalding-Jamieson, Jack, Wolff, Alexander |
| Rok vydání: |
2019 |
| Předmět: |
|
| Zdroj: |
Journal of Graph Algorithms and Applications, 25(2):643-661 (2021) |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.7155/jgaa.00576 |
| Popis: |
Consider a graph with a rotation system, namely, for every vertex, a circular ordering of the incident edges. Given such a graph, an angle cover maps every vertex to a pair of consecutive edges in the ordering -- an angle -- such that each edge participates in at least one such pair. We show that any graph of maximum degree 4 admits an angle cover, give a poly-time algorithm for deciding if a graph with no degree-3 vertices has an angle-cover, and prove that, given a graph of maximum degree 5, it is NP-hard to decide whether it admits an angle cover. We also consider extensions of the angle cover problem where every vertex selects a fixed number $a>1$ of angles or where an angle consists of more than two consecutive edges. We show an application of angle covers to the problem of deciding if the 2-blowup of a planar graph has isomorphic thickness 2. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
