The first number is the ID of a node, the following list contains the IDs of its neighbours. As a node's number of neighbours differs I need to draw a polygon map.
The problem of this approach is that for example nodes 4 and 1 are neighbours but in the Voronoi diagram they aren't because of the position of the nodes. So for me this approach failed.
Googling, I found a lot of tutorials generating maps with polygons or tiles but I haven't found out yet how I can create a map for my given data. I guess there is an approach using (multiple) hexagons/triangles/squares or a mixture to achieve what I need but I don't know what I shall search for.
Is there a keyword or an algorithm which can help me here?
The problem, as you can see, is that if you want to keep the same layout of the graph, you'll get some really curvy edges in the dual graph. Also, you'll often end up with a multigraph - a graph where some vertices have multiple edges between them. It is guaranteed to be planar though, so that's something.
Note that we create an outer "ring" to represent the outermost "vertex" - this is so we can have a nicer looking graph at the end, without the crazy curvy edges.
Also, you're going to have to do something about these edges not overlapping each other. The gap between 3 and 12 is especially problematic. These new edges may need to be bendy to make this possible. It's what you get for having a concave graph.
If the first image, where each point is a small square with certain color, is what you are searching for, you need to build the Delaunay's triangulation.
Not the answer you're looking for? Browse other questions tagged algorithm graph or ask your own question.
Graph Isomorphism > What kind of Graph is this?