Graph Reconstruction from Drawings with Crossings

Hamdy Zidan and Gerik Scheuermann


Graph drawing, Graph reconstruction, Morphological approach, Crossing edges


Graphs are used for many purposes in natural sciences, social sciences, computer science, engineering, business, and media. In some cases, graphs have been drawn by computers but digital data is lost and only the printed drawing is left. Hence, the user wants to reconstruct the graph from the drawing, e.g. a UML diagram from a drawing of an older software system where the original design is only left as documentation on paper. We offer a approach based on image processing and optical character recognition (OCR) to solve a larger sub-task of this overall problem. We reconstruct the graph topology and node labels directly from the drawing and store the result in a digital graph format. Especially, we deal with crossing edges and node labels inside outside nodes.

Important Links:

Go Back