## Complexity of finding a Eulerian path such that the image under a bijection is also a Eulerian path

Problem input: undirected graphs $$G$$, $$H$$ and a bijection $$f: E(G) \to E(H)$$
Question: Is there a Eulerian path $$p: \{1,\dots,|E(G)|\} \to E(G)$$ in $$G$$ such that $$f \circ p$$ is a Eulerian path in $$H$$?

Is this problem in $$P$$, $$NP$$-complete or maybe equivalent to some other well-known problem that isn’t known to be either yet?

The problem turned up as a special case of a more general problem first in the Bachelors thesis of another student last year and now in mine as well (I was improving some of the results of the other thesis). All other cases of the problem are now known to be either NP-hard or solvable in polynomial time, but neither one of us managed to make any progress on that case. On the other hand it feels like a much more "natural" problem than the other cases, so I think we may have missed a simple proof.

If undirected graphs are replaced by directed graphs in the problem statement there is a simple polynomial time algorithm (find a Eulerian path in the graph with vertex set $$V(G)\times V(H)$$ and edge set $$\{((v_1, w_1), (v_2, w_2)) | (v_1, v_2)=e \in E(G), f(e) = (w_1, w_2)\}$$ ignoring isolated vertices). The analogous graph for the undirected case contains 2 edges for each edge in $$G$$, so just finding a Eulerian path is no longer enough.

Posted on Categories proxies

## How are metric TSP and Eulerian cycle equivalent?

In paper : https://arxiv.org/pdf/1908.00227.pdf it is stated that

In the metric TSP problem, which we study here, the distances satisfy the triangle inequality. Therefore the problem is equivalent to finding a closed Eulerian connected walk of minimum cost.

They don’t seem to be equivalent at all, since for a complete graph of size 5, with all edge costs 1, a metric TSP solution would be of cost (and length) 5, whereas an Eulerian cycle would be of cost (and length) 10. Am I misunderstanding?

Posted on Categories proxies

## how do i know the least number of pen lifting on semi eulerian graph or eulerian graph using math formula?

he problem : Is it possible to draw a given graph without lifting pencil from the paper, however I want to know the least number of pencil lifting when the graph is not Eulerian, is there a math formula for that?

enter image description here

Posted on Categories proxies

## Non-equivalent eulerian trails in $K_{2n+1}$

Two eulerian trails of $$K_{2n+1}$$ are defined to be equivalent if the orientations obtained by orienting the edges as traversed by the trails are isomorphic as digraph. How many non-equivalent trails are there?

## Context

For context, this problem is part of my attempt to determine the path of least inertia for a free and open-source laser scanner DAC API I am developing. The following problem arises during the vector image optimisation pass. I convert the 2D vector image into a graph of 2D positions and add blank edges (i.e. transparent lines) to represent the image as a strongly connected, undirected Eulerian graph from which I should be able to determine the optimal Eulerian circuit.

## Problem

Given a strongly connected, undirected Eulerian graph (i.e. each vertex has an even degree), I’m trying to determine the Eulerian circuit that results in the minimum possible accumulative angle, where each vertex is a position in 2D space and each edge describes a straight line between the vertices.

## My Solution Attempt

My attempt at solving this was to first simplify the problem by looking at each vertex individually. We know that each vertex must have an even degree, and thus for each vertex there must be an optimal set of incoming/outgoing edge pairs (where each edge is used once) that results in a minimum accumulative angular distance. By minimum accumulative angular distance, I’m referring to the sum of the difference between the result of the difference between the angle of each incoming/outgoing edge pair and a straight line. For example, given the following vertex A and its neighbours B, C, D and E: an example of optimal pairs would be (DA, AB) and (EA, AC) as they are cumulatively the least sharp angles through which A may be traversed (and in turn would induce the least inertia), whereas the pairs (EA, AD) and (BA, AC) would be the least optimal as cumulatively they contain the sharpest angles to be traversed (resulting in the highest inertia).

Once the set of optimal pairs is determined for each vertex, I suspect the Eulerian Circuit can be created by starting at one of the vertices, picking a direction to begin and following the optimal pairs until the beginning is reached again.

## My Solution Attempt Issues

Currently however I’m running into two issues.

1. I don’t know for sure whether or not my assumption holds true for all Euler graphs (where all nodes have an even degree).
2. I’m unsure of the best approach for determining the set of optimal edge pairs for each vertex. I suspect it may be possible to represent each vertex and its edges as a sub-graph and treat the problem as finding the shortest path (where the “shorter” distances are the paths through the vertex that result in the straightest angles), but I’m struggling to come up with a sub-graph representation that would allow me to do this.

## Related Research

In section 3.4 of Accurate and Efficient Drawing Method for Laser Projection the paper describes using Hierholzer’s algorithm for finding an optimal Eulerian circuit with the amendment that during traversal of each vertex you select the unvisited edge along the angle closest to a straight line. One issue that occurs to me with this approach is that it is not clear to me that this always results in the absolute optimal circuit, only one that is probably more optimal than a naive construction without this added amendment.

## Questions

1. Is there an existing solution to the original Problem stated above? If so, is there somewhere I might read further on this?
2. If not, does my attempted solution sound like a reasonable approach? If so, do you have an idea of how I might represent the sub-graph for determining the set of edge pairs resulting in the minimum accumulative angular distance for each vertex?
3. If not, can you recommend an approach I might be able to take to make progress on solving the previously mentioned Problem?

Posted on Categories proxies

## Deformation gradient conservation law from Larangian to Eulerian formulation

In the following, I use the standard notation for (solid) mechanics and conservation laws, i.e. $$F$$ the formation gradient, $$H$$ the cofactor, $$v$$ the velocity field and $$J$$ the Jacobian. Moreover, $$X$$ is for the initial configuration where functions and fields are expressed using a bar and $$x$$ is for the mapped {current) configuration.

The rate of deformation gradient can be expressed as: $$\frac{\partial F}{\partial t} = \nabla \bar{v}$$.

Now I know how to derive the total (TLF) $$\frac{d}{dt}\int_V F \; dV = \int_{\partial V} \bar{v}\otimes N \; dA$$ and updated (ULF) $$\int_{v(t)} J^{-1} \left.\frac{\partial F}{\partial t}\right\vert_{X} \; dv = \int_{v(t)} \nabla\cdot (v\otimes H) dv$$ lagrangian formulations.

I would like to get, if it exists, the Eulerian formulation of the above, as well as the ALE and Total ALE formulation of it.

To do so, I tried to start from TLF, I switch to the current configuration $$v(t)$$ using $$J$$ and I use the Reynold’s transport theorem to get rid of the total time derivative on the integral and to get the convective term. I end up with:

$$\int_{v(t)} \frac{\partial J^{-1}F}{\partial t} + \nabla\cdot(J^{-1}F\otimes v) \; dv = \int_{v(t)} \nabla\cdot (v\otimes H^{-1}) \; dv$$

Are the mathematics correct? And can I reach these formulations? May I say that I prefer integral forms..