Can this graph be redrawn after merging two specific vertices and remain planar?

68 Views Asked by At

A directed graph was created in a manner different from the normal abstractions of graph theory. It can be found on the page https://www.rootgame.net/factions and is also shown below

enter image description here

with some vertices (the circles) having an image instead of the normal text. The edges there do not just consist of straight lines and are allowed to bend in order to avoid crossing other edges. One vertex (the raccoon, called the "Vagabond" in the boardgame Root) is shown duplicated. Is it possible to redraw that graph, retaining all the information from the other connections, while consolidating the two duplicate circles into one and not requiring an extra dimension to avoid edges intersecting? An answer to another question here said that a planar graph with n vertices can have at most 3n - 6 edges, and this one has 22 vertices (if one counts the starting point with only one edge, removing it results in 21) and I think 29 edges.

1

There are 1 best solutions below

2
On

A graph is not planar if it has a $K_{3,3}$ minor (see Wagner's theorem). If we merge the two vertices, then this graph will gain a $K_{3,3}$ minor. Below, I've marked three vertices each with labels $1$ and $2$ to denote the bipartition, and filled in the edges in red. enter image description here