![]() |
Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020
DOI: 10.7155/jgaa.00576
Angle Covers: Algorithms and Complexity
Vol. 25, no. 2, pp. 643-661, 2021. Regular paper.
Abstract 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.
![]() |
Submitted: June 2020.
Reviewed: November 2020.
Revised: January 2021.
Reviewed: February 2021.
Revised: March 2021.
Accepted: September 2021.
Final: October 2021.
Published: November 2021.
|
Journal Supporters
|