title: How to untangle a graph?
body: <p>I have an API that sends me the information of the following source graph (You may assume A, B &amp; C to have a common parent)</p>
  
  <p><a href="https://i.stack.imgur.com/AIx5z.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/AIx5z.png" alt="Constructed graph"></a></p>
  
  <p>as the following JSON (ignore the string and number values, purely representational; order of the keys is non-deterministic)</p>
  
  <pre><code>{
      "f": {
          "childOf": {
              "d": "own"
          },
          "data": 6
      },
      "d": {
          "childOf": {
              "b": "foster"
          },
          "data": 4
      },
      "a": {
          "data": 1
      },
      "h": {
          "childOf": {
              "f": "step"
          },
          "data": 8
      },
      "g": {
          "childOf": {
              "e": "foster",
              "a": "own"
          },
          "data": 7
      },
      "c": {
          "data": 3
      },
      "e": {
          "childOf": {
              "c": "step"
          },
          "data": 5
      },
      "b": {
          "data": 2
      },
      "i": {
          "childOf": {
              "a": "step"
          },
          "data": 9
      }
  }
  </code></pre>
  
  <p>For building the graphical representation from the json, I wrote a function that gives me the levels at which each node occurs, based on the data provided by the childOf property. The result is something like</p>
  
  <pre><code>[
      ["a", "b", "c"],
      ["i", "d", "e"],
      ["g", "f"],
      ["h"]
  ]
  </code></pre>
  
  <p>which, while vertically correct, has no consideration for the left to right order of the nodes in the source representation. This sometimes leads to the following (tangled) graph (see red and blue edges)</p>
  
  <p><a href="https://i.stack.imgur.com/SiIQo.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/SiIQo.png" alt="Tangled Reconstruction"></a></p>
  
  <p>How would I obtain an untangled graph from information in the above JSON format? (knowing that the source representation is always untangled, and hence an untangled solution must exist)</p>
  
  <p>Idea 1: An idea I have for the implementation is DFS with priority. For example, if the DFS starts at A and reaches G, it should prioritise E and subsequently C when it chooses siblings to dive for the next branch.</p>