Graph drawing beyond planarity: some results and open problems.
Giuseppe Liotta · Italian Conference on Theoretical Computer Science · 2014
We briefly review some recent findings and outline some emerging research directions about the theory of “nearly planar” graphs, i.e. graphs that have drawings where some crossing configurations are forbidden. 1 Graph drawing beyond planarity Recent technological advances have generated torrents of relational data that are hard to display and visually analyze due, mainly, to their large size. Application domains where this need is particularly pressing include Systems Biology, Social Network Analysis, Software Engineering, and Networking. What is required is not simply an incremental improvement to scale up known solutions but, rather, a quantum jump in the sophistication of the visualization systems and techniques. New research scenarios for visual analytics, network visualization, and human-computer interaction paradigms must be identified; new combinatorial models must be defined and their corresponding theoretical problems must be computationally investigated; finally, the theoretical solutions must be experimentally evaluated and put into practice. Therefore, a substantial research effort in the graph drawing and network visualization communities started from the following considerations. The Planarity Handicap. The classical literature on graph drawing and network visualization showcases elegant algorithms and sophisticated data structures under the assumption that the input relational data set can be displayed as a network where no two edges cross (see, e.g., [14,35,36,40]), i.e. as a planar graph. Unfortunately, almost every graph is non-planar in practice and various experimental studies have established that the human ability of understanding a diagram is dramatically affected by the type and number of edge crossings (see, e.g., [42,43,48]). Combinatorial Topology vs. Algorithmics. A topological graph is a drawing of a graph in the plane such that vertices are drawn as points and edges are drawn as simple arcs between the points. Extremal theory questions such as “how many edges can a certain type of non-planar topological graph have?” have been investigated by mathematicians for decades, typically under the name of Turan-type problems. However, the corresponding computational question: “How efficiently can one compute a drawing Γ of a non-planar graph such that Γ is a topological graph of a certain type?” has been surprisingly disregarded by the algorithmic community until very recent years.