Short answer. Your question, strictly construed, does not have a noteworthy answer (I think), and there is good reason that it doesn't: your graph $H$ 'is'1 just the Levi graph(=bipartite incidence4 graph) of $G$. Using directed edges to encode the non-incidences is redundant because in an incidence graph (at least if you are working in material set theory) the vertices are usually meaningfully labelled by the very constituents of the original incidence structure, so all the information about the original not-necessarily bipartite graph is still there, even if you refrain from adding edges for non-incidences. In a sense, if you start adding edges for non-incidences into a Levi graph, you spoil it, and then have to make amends by adding all the edges, and then start over with the encoding of your original graph, e.g. by equipping it with direction, like you did. In that sense, this is overly complicated. (I recognize that you may have private reasons to insist that $H$ have the type 'digraph', I just do not know these reasons.)
If you insist for whatever reasons that the result of your 'derived graph' be a digraph, then (I think) there does not exist a noteworthy literature reference.
Recommendation. Re you comment
[...] I see that I have to come up with a precise definition.
If you do not insist that the result of you operation be a "digraph" (in the sense of e.g. the monograph of Bang-Jensen and Gutin), then you do not need to "come up" with a definition. Then it is sufficient to simply0 say
- For any undirected simple graph $G=(V,E)$, let $W(G)$ be the Levi graph ($=$ bipartite incidence graph) of $G$. (I.e. $W(G)$ has vertex set $V\cup E$ and undirected edges precisely the 2-sets $\{v,e\}$ with $v\in e$.) ${\qquad}$ (LG)
If you insist that the result be a digraph, then that's another matter, and then you may use the definition you already gave. (I did not say said definition of yours was imprecise, it was merely very usually written, to the point of being almost-wrong at places.)
My recommendations would be to try to keep reasonably close to usual graph-theoretic notation, rather than "to come up" with something new. Of course you have a right to unusual notation, it will simply make it less likely that you will be understood.
A. Weil put it well in his textbook "Foundations of Algebraic Geometry", American Mathematical Society, 1946, Introduction:
in a treatment, of this kind, particular attention must be and has been given to the language and, the definitions. Of course every mathematician has a right to his own language - at the risk of not being understood; and the use sometimes made, of this right by our contemporaries almost suggests that the same fate is being prepared for mathematics as once befell, at Babel, another of man's great achievements. A choice between equivalent definitions is of small moment, and two theories which consist of the same theorems are to be regarded as identical, whatever their starting points. But in such a subject as algebraic geometry, where earlier authors left many terms incompletely defined, and were wont to make (sometimes implicitly) assumptions from which we wish to be free, all terms have to be defined anew, and to attach precise meanings to them is a task not unworthy of our most solicitous attention. Our chief object here must be to conserve and complete the edifice bequeathed to us by our predecessors.
which reads eerily relevant to some parts of mathematics today.
(Note also: somewhat ironically, despite the author's well-meaning attempt, his language for algebraic geometry has largely been replaced by the one from the EGA and SGA.)
Detailed answer.
(0) Your question does not have an answer if very strictly construed to mean that you are asking for a usual term and a notable treatment of the use of directed complete bipartite graphs as incidence-graph-like auxiliary graphs. In other words, your question does not have an answer if you insist that the literature reference (0.0) is noteworthy, (0.1) match your specifications up to and including the data-types you chose.
Yet: there is an equivalent definition and you should use that (I think) unless you have reasons to insist that the result of your operation be a digraph.
(1) Beware that in the literature the following distinction is often glossed over: (1.0) "abstract incidence graph of a given undirected simple graph" in the strictest sense (i.e., said incidence graph is again a graph, no further decorations,) and (2.1) "incidence graph in which the vertices are still the parts of the given original, so that no information is lost".
Authors sometimes only give the definition of the incidence graph $I(G)$, in terms of the (names of the) vertices and edges of the given graph $G$, but do not say whether they assume that the vertices are labelled by the data by which $G$ was given.
More clearly, formally, I think one can meaningfully distinguish theh following.
Let $G=(V,E)$ be a given undirected simple and, as mathematician working with material set theory are wont to say, 'labelled' graph. That is, $G$ is a graph as e.g. in Diestel, Graph Theory, 4th ed.
Then
the graph $W(G)$ from (LG) above is again a such an undirected simple labelled graph
$W(G)$ is not a 2-colored graph. That is another type: a 2-colored graph is a pair consisting of a graph $G$ and a specified set-map $c\colon V(G)\rightarrow S$ where $S$ is a 2-element set.
$W(G)$ always is a 2-colorable graph. That is evident.
$W(G)$ admits a 'canonical' (which, luckily, is a not a formally defined term, leaving some leeway of expression) 2-coloring $c$, namely the unique set-map $c\colon V(W(G))\rightarrow\{V,E\}$ with $c(v)=V$ and $c(e)=E$, i.e., the two-element color-set used here is $\{V,E\}$, a set which exists on account of the Axiom of Pairing of the Zermelo-Fraenkel axioms.
This is a subtle variant of the labelled-vs-unlabelled graph distinction: while both these terms are reasonably standardly defined, there is no standard definition for "labelled graph with labels that we care about", so to speak.
Please note:
many mathematicians would wince at spelling out the above, and in particularl at 'coloring' vertices by a set containing them, though probably there is nothing wrong with that logically
alternatives to the above are either to make two arbitrary choices, namely (0) which two-element set to use for the vertex-coloring, (1) which of the two elements of the arbitrarily chosen two-set to use for the vertex-coloring
category theory offers an alternative to formalize such ideas, in particular, you might find it useful (your mileage may vary) to use category theory to formalize you TSP heuristic and in particular your operation $H$.
(3) The graph $H(N,A)$, to use use your notation (that I warn you against), contains (and with an obvious encoding) the same information as what is usually called the bipartite incidence graph (shorter, usual2 less pleonastic3, yet also less descriptive term: Levi graph) of the graph $G$, with $G$ being viewed as an incidence structure $(V,E,I)$ having the (elements of the) set $V$ for its points, the (elements of the) set $E$ for its lines, and $I\subseteq V\times E$ given by $(v,e)\in I$ $\Leftrightarrow$ $v\in e$
Footnotes
0 Please be careful though: often, even more often than not I would say, in the literature a Levi graph is considered to be a 2-colored graph (not to be confused with 2-colorable graph). In that sense, strictly speaking a Levi graph in the literature, unlike in the suggestion above, is often not a graph in any of the usual senses of 'graph' whihch never allow attaching custom data to vertices, a Levi graph is often, unlike in my suggestion above, considered to be a 2-colored graph. Example from the the peer reviewed literature is
Dragan Marušič,Tomaž Pisanski, Steve Wilson: European Journal of Combinatorics, Volume 26, Issues 3–4, April–May 2005, Pages 377-385, wherein on p. 378-379 one finds:
and the illustration (which also illustrates the Coxeter-citation given in this answer, by the way)
So, if the precise formalization matters to you, it will be necessary to watch out for whether Levi graph is used to mean 'bicolored bipartite incidence graph' or 'bipartite incidence graph'($=$incidence graph)$\subset$(class of graphs).
1 In a rather informal sense of 'is', similar to 'is equivalent to'. To give a precise sense to 'is equivalent to', one could take the following route:
- first of all, agree that the following approach is 'the' right one (an agreement which is already hard enough to reach),
- then agree which 'category $\mathsf{C}$ of undirected simple graphs' to use (and there are several such),
- then agree upon a category $\mathsf{C}_0$ having as objects bipartite digraphs,
- then agree upon a category $\mathsf{C}_1$ having as objects 2-colored bipartite undirected simple graphs,
- define a functor $F_0\colon\mathsf{C}\rightarrow\mathsf{C}_0$ whose object-class-function equals the class-function adumbrated in the OP (in short: extend your $H$-operation to a functor),
- then define a functor $F_1\colon\mathsf{C}\rightarrow\mathsf{C}_1$ whose
object-class-function takes any undirected simple graph to its vertex-edge-Levi-graph,
- finally prove that $F_0$ and $F_1$ are isomorphic functors.
While such an approach is very useful, there does not exist an agreement how to carry it out. No such agreement exists, and probably cannot exist in view of insufficient criteria how to decide what is essential for you. It does not seem worthwhile to get into an argument about it.
2 To give an early example of Levi graphs being used let met cite H. S. M. Coxeter, Self-dual configurations and regular graphs, Bull. Amer. Math. Soc., Volume 56, Number 5 (1950), 413-455, wherein on p. 414 we have the following illustration (retouched to hide distracting information)
Coxeter introduces the Levi graph here:
3 The (very usual) technical compound term "bipartite incidence graph" is the same type of pleonasm as "bicyclic mountain bike". An "incidence graph" (to me at least, and to many others) is always bipartite. Therefore, "bipartite incidence graph" is pleonastic. However, neither the compound "incidence graph", nor "bipartite graph" are pleonastic terms, only upon taking the sort-of-union $\{$ incidence graph $\}$ $\cup$ $\{$ bipartite graph $\}$ $\approx$ $\{$ bipartite incidence graph $\}$ one ends up with a pleonasm.
Similarly,
'mountain bike' lexically exists.
The compound 'mountain bike' is not pleonastic at all; by far not every bike is a mountain bike, in any reasonable sense.
The compound 'bicyclic mountain bike' is pleonastic, in a reasonably clear sense: no usual mountain bike has a number of wheels other than 2.
There exist bikes which are non-bicyclic, in that there exist unicycles. So this is an example of what I would call an
'a n N'-pleonasm
Definition. An 'a n N' pleonasm is a compound wherein 'a' is an adjective, 'N' is a noun, 'n N' must be a lexically existant noun compound, 'n N' must be non-pleonastic, and 'a N' must be reasonably meaningful and non-pleonastic too, while 'a n N' itself must be reasonably meaningful yet pleonastic in that every 'n N' is 'a'.
Again, it is only pleonastic to add the 'a' to the 'n N'. It is not pleonastic to add 'a' to 'N', nor to add 'n' to 'N'. (Note that 'bicyclic bike', while unusual, is not pleonastic, and appropriate in certain contexts, in view of unicycles or training wheels.)
4 To give an example from the literature that the notation $v\in e$ I recommended elsewhere is usual, consider e.g. Diestel, Graph Theory, 4th edition, p. 2, which gives a way of putting it which is usual nowadays:
Incidentally, this also gives one more reason why the notation $G(V,E)$ in the original OP is not to be recommended: it is similar to $E(X,Y)$, hence will read to some as if you had named an edge set by '$G$', a vertex by '$V$' and another vertex set by '$E$', which is confusing (to me).
