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.

  • $\begingroup$ It seems that a 3-star and a 3-cycle have the same sequences. $\endgroup$ – Ilya Bogdanov May 24 '16 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$ – user1747134 May 24 '16 at 12:22
  • $\begingroup$ Also on cs.se: cs.stackexchange.com/questions/57810/…. $\endgroup$ – Yuval Filmus May 24 '16 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$ – Klaus Draeger May 24 '16 at 13:22
  • $\begingroup$ dx.doi.org/10.1016/j.dam.2011.02.009 $\endgroup$ – Steve Huntsman May 24 '16 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.