| KEYWORD |
Automated graph visualization and rendering
keywords CIRCUITS, GRAPH, RENDERING, VISUALIZATION
Reference persons STEFANO GRIVET TALOCIA
Research Groups EMC Group (Electromagnetic Compatibility)
Description A graph is a set of elements (nodes or vertices) that can be connected to each other by lines (edges or branches). The application areas of graph theory are extremely wide and differentiated: a graph provides the ideal tools for describing the topology of electrical and electronic circuits, telecommunications networks, transport networks (roads, railways) and even networks of social interactions between individuals or groups.
In order to define a graph, it is sufficient to specify the set of its nodes and which pair of nodes each edge is connected to. However, in many applications it is also useful to visualize or render the graph, which in turn requires the knowledge of the coordinates of each node and the path of each edge, intended as a curve in the plane or space. Only this information allows to draw the graph, making the underlying structure evident "at a glance". In some applications (for example, road or rail transport networks), the node coordinates are given (the stations to be reached), whereas the path of the edges and even which edges to consider may be design parameters (for example, to ensure that every station can be reached). In other applications, instead, the graph is known only by an abstract definition, and completely lacks the information needed for its visualization. For example, when designing a complex electronic system consisting of a large number of components that need to be placed on a printed board and subsequently connected to each other, appropriate place and route algorithms are needed, which in a completely automatic way define the position of the various components and the path of the respective connections, so as to optimize appropriate parameters (for example, the total area occupied or the total length of the links). For such applications, the concept of "visualization" coincides with the CAD design of the circuit layout.
This thesis aims to study the existing algorithms for automated graph visualization, and to develop a software package in the Matlab environment that realizes the prominent ones. Particular attention will be devoted to planar graphs (which can be drawn on a plane without edge crossings), given the high application interest (in particular, in circuit theory). This thesis work will also involves the modification of existing algorithms to include, by appropriate mathematical formulations, those constraints that allow for clear and well-balanced visual aesthetics. These constraints depend on the specific applications for which the visualization is determined. The applications that will be considered depend on the candidate and his/her interests.
Required skills Predisposizione per la formalizzazione matematica di problemi e algoritmi. Programmazione in ambiente Matlab. Utile conoscenza di linguaggio C/C++ per utilizzare librerie software
Deadline 07/10/2021
PROPONI LA TUA CANDIDATURA