Graph Reconstruction from Drawings without Crossings

Hamdy Zidan and Gerik Scheuermann


Image Segmentation, Mathematical Morphology, Graph Drawing, Graph Reconstruction


Graphs are used for many purposes in science, engineering, and business. In some cases, graphs have been drawn by computers but digital data is lost and only the printed drawing is left. An example would be old UML diagrams of a software system. Hence, the user wants to reconstruct the graph from the drawing. This paper deals with a special case where an drawing without crossing edges of such a graph is given. The vertices of the graph are assumed to be larger regions as is typical, e.g., for UML class diagrams. We show how edge detection, morphological operators, and region growing lead to a segmentation of such images that allows to reconstruct the graph fromsuch drawings. The method is tested with some examples.

Important Links:

Go Back