In this paper, magic labelings of graphs are considered. These are labelings of the edges with integers such that the sum of the labels of incident edges is the same for all vertices. We particularly study positive magic labelings, where all labels are positive and different. A decomposition in terms of basis-graphs is described for such labelings. Basis-graphs are studied independently. A characterization of an algorithmic nature is given, leading to an integer linear programming problem. Some relations with other graph theoretical subjects, like vertex cycle covers, are discussed.