Geodesic
Angle Covers: Algorithms and Complexity
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020 , Tome 25 (2021) no. 2, pp. 643-661.

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

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 without a degree-3 vertex 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.
DOI : 10.7155/jgaa.00576
Keywords: angle cover, NP-hard, matching 
@article{JGAA_2021_25_2_a3,
     author = {William Evans and Ellen Gethner and Jack Spalding-Jamieson and Alexander Wolff},
     title = {Angle {Covers:} {Algorithms} and {Complexity}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {643--661},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2021},
     doi = {10.7155/jgaa.00576},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00576/}
}
TY  - JOUR
AU  - William Evans
AU  - Ellen Gethner
AU  - Jack Spalding-Jamieson
AU  - Alexander Wolff
TI  - Angle Covers: Algorithms and Complexity
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 643
EP  - 661
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00576/
DO  - 10.7155/jgaa.00576
LA  - en
ID  - JGAA_2021_25_2_a3
ER  - 
%0 Journal Article
%A William Evans
%A Ellen Gethner
%A Jack Spalding-Jamieson
%A Alexander Wolff
%T Angle Covers: Algorithms and Complexity
%J Journal of Graph Algorithms and Applications
%D 2021
%P 643-661
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00576/
%R 10.7155/jgaa.00576
%G en
%F JGAA_2021_25_2_a3
William Evans; Ellen Gethner; Jack Spalding-Jamieson; Alexander Wolff. Angle Covers: Algorithms and Complexity. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 14th International Conference and  Workshops on Algorithms and Computation, WALCOM 2020
					, Tome 25 (2021) no. 2, pp. 643-661. doi : 10.7155/jgaa.00576. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00576/

Cité par Sources :