0
$\begingroup$

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of vertices in the graph, but it's given that each edge in each given sequence shares a vertex with the edge next to it in the sequence. We could further assume, that all the sequences start with the same edge.

Ideally, I would need an algorithm to reconstruct the graph.

Has such problem been already studied or does anyone see a way to transform it to another known problem? So far, I can only think of genetic algorithms.

$\endgroup$
5
  • $\begingroup$ It seems that a 3-star and a 3-cycle have the same sequences. $\endgroup$ May 24, 2016 at 12:17
  • $\begingroup$ Thanks for pointing that out. If there is not an unique solution, the algorithm could return one of them or better the complete set of possible soulutions. $\endgroup$ May 24, 2016 at 12:22
  • $\begingroup$ Also on cs.se: cs.stackexchange.com/questions/57810/…. $\endgroup$ May 24, 2016 at 12:45
  • $\begingroup$ Is the set of sequences assumed to be exhaustive in the sense that every pair of edges with a common end appear in one of them? If so, the sequences determine the line graph of the original graph, which can be reconstructed except in the special case mentioned by Ilya Bogdanov. $\endgroup$ May 24, 2016 at 13:22
  • $\begingroup$ dx.doi.org/10.1016/j.dam.2011.02.009 $\endgroup$ May 24, 2016 at 15:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.