7/17/2023 0 Comments Poincare disk graph theory![]() In order to obtain a tool that allows for fluid movements through drawings of very large graphs, a client-server system might be necessary, that shifts costly (pre-)computations to the server and only submits the currently required data to the client. Given a graph, the tool should compute the hyperbolic coordinates of the nodes (using a C++ program that is already available) and display the resulting drawing to the user who can then move around in it. The goal of this project is to build a web application that presents an interactive visualization of graphs in the hyperbolic plane using the above models. Consequently, such a visualization can be a powerful tool to understanding properties of networks with an underlying hyperbolic geometry. Using the fish-eye view, however, one can look at a specific part of the network in closer detail while still maintaining some sense of the larger structure. On the other hand, while zooming in and panning around reveals the details of parts of the network, it also loses the overall structure of the graph. Usually, when visualizing networks with thousands of nodes it is hard to locate the smaller parts that are of special interest. Consequently, a visualization of the hyperbolic space results in a fish-eye view, as can be seen in the image below. In the latter space expands exponentially. The major difference between the well-known Euclidean geometry and hyperbolic geometry is the expansion of space. Under this assumption the shortest path between two nodes can be found in sub-linear running time and even the NP-hard problem of finding the largest clique in the network can be solved in polynomial time. One approach to understand this gap is to analyze a graph model that closely resembles the networks that occur in the real world and exploiting properties of the model that set it apart from the theoretical worst-case.Ī very promising model assumes that a network has an underlying hyperbolic geometry and it was shown that many complex real-world networks actually do. ![]() The reason for this is that the instances that are found in the real world rarely resemble the worst-case instances used for the theoretical analysis. In the Poincaré case, lines are given by diameters of the circle or arcs.When analyzing the running time of graph algorithms, it is often observed that there is a huge gap between theory and practice. Remember that in the half-plane case, the lines were either Euclidean lines, perpendicular onto the real line, or half-circles, also perpendicular onto the real line. Moreover, every such intersection is a hyperbolic line. With a circle in the extended complex plane perpendicular to the unit circle bounding Just like in the half-plane model, we will look first at lines in this model. Note that we are still in the complex plane. The underlying space of this model is the open unit disk As you will see at the end of this page, it is this model that appears in Escher's work. You may ask yourself why is it necessary to do that? The reason is that this model is more useful, as it gives more insight and we can make a better use of the apparatus from the complex analysis. This model is constructed starting from the previous one. The second model that we use to represent the hyperbolic plane is called the Poincaré disk model, named after the great French mathematician, Henri Poincaré (1854 - 1912). The Poincaré disk model for the hyperbolic plane The Poincaré model for the hyperbolic plane, Section 7ħ.
0 Comments
Leave a Reply. |