Solving The House Drawing Problem With Graph Theory Algorithms

Question

I was recently given the challenge of drawing a house with an x in the middle without lifting my pen, and without retracing any lines. Link to problem

The link above begins to dive into some of the graph theory related to the problem, however there is no mention of how one might go about solving this problem using graph theory algorithms.

What algorithms could be used here, and what would be the correct way to formulate this problem using graph theory language?

Answer 1

Two specific algorithms for constructing an Eulerian path are mentioned in the Wikipedia article on Eulerian paths. These are Fleury's algorithm and Hierholzer's algorithm.

Note that an algorithm that only finds an Euler cycle can also find an Euler trail by augmenting the graph with another edge that joins the 2 vertices that have an odd degree, then rotating the solution so that the added edge is first or last, then removing this edge from the solution found.