Dr. Tamara Mchedlidze

We study the upward point-set embeddability of digraphs on one-sided convex point sets with at most 1 bend per edge. We provide an algorithm to compute a 1-bend upward point-set embedding of outerplanar st-digraphs on arbitrary one-sided convex point sets. We complement this result by proving that for every there exists a 2-outerplanar st-digraph G with n vertices and a one-sided convex point set S so that G does not admit a 1-bend upward point-set embedding on S.

We consider hypergraph visualization that represent vertices as points and hyperedges as lines with few bends passing through points of their incident vertices. Guided by point-line incidence theory we show several theoretical results: if every vertex is part of at most two hyperedges, then we can find such a visualization without bends. There exist hypergraphs with three vertices per hyperedge and three hyperedges incident to each vertex requiring an arbitrary number of bends. It is∃ R-hard to decide whether an arbitrary hypergraph can be visualized without bends. This only answers some interesting questions for such visualizations and we conclude with many open research questions.

A pseudo-triangle is a simple polygon with exactly three convex vertices, and all other vertices (if any) are distributed on three concave chains. A pseudo-triangulation~ of a point set~ in~ is a partitioning of the convex hull of~ into pseudo-triangles, such that the union of the vertices of the pseudo-triangles is exactly~. We call a size-4 pseudo-triangle a dart. For a fixed , we study -dart pseudo-triangulations (-DPTs), that is, pseudo-triangulations in which exactly faces are darts and all other faces are triangles. We study the flip graph for such pseudo-triangulations, in which a flip exchanges the diagonals of a pseudo-quadrilatral. Our results are as follows. We prove that the flip graph of -DPTs is generally not connected, and show how to compute its connected components. Furthermore, for -DPTs on a point configuration called the double chain we analyze the structure of the flip graph on a more fine-grained level.

Network visualization is one of the most widely used tools in digital humanities research. Networks have been used to study the structure of social groups, the circulation of texts, the relation of words within a text to one another, and countless other structures that are employed in digital humanities research. The idea of uncertain or "fuzzy" data is also a core notion in digital humanities research. Yet network visualizations in digital humanities do not always prominently represent uncertainty. In this article, we review some of the principles for visualizing uncertainty of different kinds and consider how these visualizations could be used in digital humanities research. We focus on elements that can be integrated into the network diagram, rather than the displayed data, or accompanying diagrams. We show that, rather than being unique to the digital humanities, uncertainty in this realm is in many ways analogous to the concept and uses of uncertainty in other disciplines; we also show how techniques for visualizing uncertainty in fields like climate science and bioinformatics could be used to represent more prominently some of the types of uncertainty that we find in humanities data.

A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be -hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic -approach in the number of popular faces.

Mutual coherence is a measure of similarity between two opinions. Although the notion comes from philosophy, it is essential for a wide range of technologies, e.g., the Wahl-O-Mat system. In Germany, this system helps voters to find candidates that are the closest to their political preferences. The exact computation of mutual coherence is highly time-consuming due to the iteration over all subsets of an opinion. Moreover, for every subset, an instance of the SAT model counting problem has to be solved which is known to be a hard problem in computer science. This work is the first study to accelerate this computation. We model the distribution of the so-called confirmation values as a mixture of three Gaussians and present efficient heuristics to estimate its model parameters. The mutual coherence is then approximated with the expected value of the distribution. Some of the presented algorithms are fully polynomial-time, others only require solving a small number of instances of the SAT model counting problem. The average squared error of our best algorithm lies below 0.0035 which is insignificant if the efficiency is taken into account. Furthermore, the accuracy is precise enough to be used in Wahl-O-Mat-like systems.

Robust Genealogy Drawing Page 1 1 Beyond Planarity: A Spring-Based Approach Simon van Wageningen · Tamara Mchedlidze · Alexandru Telea Heuristic The u to av struc a gra huma with f Draw can b graph affirm graph plana graph works probl that a Yet, t layou spring drawi The ultimate goal when constructing a readable graph drawing is to avoid clutter that prevents viewers from grasping the structure of the graph We know humans perform better on user tasks in drawings with fewer crossings [13] and tend to prefer such drawings [12, 6] Testing whether a graph can be drawn without edge crossings [7], ie in a planar way, as well as constructing its planar drawing [14], can be done in linear time In practice, however, graphs are rarely planar, but can still have a planar substructure and thus be nearly planar. Can we draw graphs in a near-planar manner? Formal definitions of near-planarity lead to hard …

Planar drawings of graphs tend to be favored over non-planar drawings. Testing planarity and creating a planar layout of a planar graph can be done in linear time. However, creating readable drawings of nearly planar graphs remains a challenge. We therefore seek to answer which edges of nearly planar graphs create clutter in their drawings generated by mainstream graph drawing algorithms. We present a heuristic to identify problematic edges in nearly planar graphs and adjust their weights in order to produce higher quality layouts with spring-based drawing algorithms. Our experiments show that our heuristic produces significantly higher quality drawings for augmented grid graphs, augmented triangulations, and deep triangulations. CCS Concepts

The page-number of a directed acyclic graph (a DAG, for short) is the minimum k for which the DAG has a topological order and a k-coloring of its edges such that no two edges of the same color cross, ie, have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number 2 is NP-complete and proved that recognizing DAGs with page-number 6 is NP-complete (Heath and Pemmaraju (1999)[15]). Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number k is NP-complete, for every k≥ 3 (Binucci et al.(2019)[6]). In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for st-planar graphs and planar posets.

A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, which asks whether a graph admits a kUBE, was introduced in 1999 by Heath, Pemmaraju, and Trenk (SIAM J Comput 28(4), 1999). In a companion paper, Heath and Pemmaraju (SIAM J Comput 28(5), 1999) proved that the problem is linear-time solvable for and NP-complete for . Closing this gap has been a central question in algorithmic graph theory since then. In this paper, we make a major contribution towards a definitive answer to the above question by showing that kUBE Testing is NP-complete for , even for st-graphs, i.e., acyclic directed graphs with a single source and a single sink. Indeed, our result, together with a recent work of Bekos et al. (Theor Comput Sci …

While 2D projections are established tools for exploring high-dimensional data, the effectiveness of their 3D counterparts is still a matter of debate. In this work, we address this from a multifaceted quality perspective. We first propose a viewpoint-dependent definition of 3D projection quality and show how this captures the visual variability in 3D projections much better than aggregated, single-value, quality metrics. Next, we propose an interactive exploration tool for finding high-quality viewpoints for 3D projections. We use our tool in an user evaluation to gauge how our quality metric correlates with user-perceived quality for a cluster identification task. Our results show that our metric can predict well viewpoints deemed good by users and that our tool increases the users’ preference for 3D projections as compared to classical 2D projections.

A mixed s-stack q-queue layout of a graph consists of a linear order of its vertices and a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. In 2017, Pupyrev disproved this conjecture by demonstrating a planar partial 3-tree that does not admit a mixed 1-stack 1-queue layout.In this work, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees, also known as series-parallel graphs. We conclude this by means of a stronger result, stating that the conjecture does not hold, even in the more general union and local settings. In the former, crossings (nestings) are allowed in the stack (queue) as long as the involved edges belong to different connected components of the subgraph induced by …

Planar graph drawings tend to be aesthetically pleasing. In this poster we explore a Neural Network's capability of learning various planar graph classes. Additionally, we also investigate the effectiveness of the model in generalizing beyond planarity. We find that the model can outperform conventional techniques for certain graph classes. The model, however, appears to be more susceptible to randomness in the data, and seems to be less robust than expected.

In this paper we study metaphoric maps of dynamic vertex-weighted graphs. Dynamic operations on such graphs allow a vertex to change the weight, vertices and edges appear and disappear. In the metaphoric map this is viewed as country shrink and growth, appearance and disappearance and change in the country adjacency. We present a force-based algorithm that supports these operations. In the design of the algorithm we prioritize the dynamic stability of the map, the accuracy in the size of countries and low complexity of the polygons representing the countries. We evaluate the algorithm based on the state-of-theart quality metrics for randomly generated inputs of various complexity.

We introduce and study level-planar straight-line drawings with a fixed number  of slopes. For proper level graphs (all edges connect vertices of adjacent levels), we give an -time algorithm that either finds such a drawing or determines that no such drawing exists. Moreover, we consider the partial drawing extension problem, where we seek to extend an immutable drawing of a subgraph to a drawing of the whole graph, and the simultaneous drawing problem, which asks about the existence of drawings of two graphs whose restrictions to their shared subgraph coincide. We present -time and -time algorithms for these respective problems on proper level-planar graphs. We complement these positive results by showing that testing whether non-proper level graphs admit level-planar drawings with  slopes is NP-hard even in restricted cases.

In geographic data analysis, one is often given point data of different categories (such as facilities of a university categorized by department). Drawing upon recent research on set visualization, we want to visualize category membership by connecting points of the same category with visual links. Existing approaches that follow this path usually insist on connecting all members of a category, which may lead to many crossings and visual clutter. We propose an approach that avoids crossings between connections of different categories completely. Instead of connecting all data points of the same category, we subdivide categories into smaller, local clusters where needed. We do a case study comparing the legibility of drawings produced by our approach and those by existing approaches. In our problem formulation, we are additionally given a graph G on the data points whose edges express some sort of proximity …

For a planar graph G and a set of simple paths in G, we define a metro-map embedding to be a planar embedding of G and an ordering of the paths of along each edge of G. This definition of a metro-map embedding is motivated by visual representations of hypergraphs using the metro-map metaphor. In a metro-map embedding, two paths cross in a so-called vertex crossing if they pass through the vertex and alternate in the circular ordering around it. We study the problem of constructing metro-map embeddings with the minimum number of crossing vertices, that is, vertices where paths cross. We show that the corresponding decision problem is NP-complete for general planar graphs but can be solved efficiently for trees or if the number of crossing vertices is constant. All our results hold both in a fixed and variable embedding settings.

This report describes the 24th Annual Graph Drawing Contest, held in conjunction with the 25th International Symposium on Graph Drawing (GD’17) in Boston, United States of America. The purpose of the contest is to monitor and challenge the current state of the art in graph-drawing technology.

We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set S has size at least the number of vertices in the tree. For the special case where the tree is a path P we show that: (a) If S is one-sided convex, the number of UPSE s equals the number of maximal monotone paths in P. (b) If S is in general position and P is composed by three maximal monotone paths, where the middle path is longer than the other two, then it always admits an UPSE on S. We show that the decision problem of whether there exists an UPSE of a directed tree with n vertices on a fixed point set S of n points is NP-complete, by relaxing the requirements of the previously known result which relied on the presence of cycles in the graph, but instead fixing position of a single vertex. Finally, by allowing extra points, we guarantee that each directed caterpillar on n vertices and with k …

In an upward planar 2-slope drawing of a digraph, edges are drawn as straight-line segments in the upward direction without crossings using only two different slopes. We investigate whether a given upward planar digraph admits such a drawing and, if so, how to construct it. For the fixed embedding scenario, we give a simple characterisation and a linear-time construction by adopting algorithms from orthogonal drawings. For the variable embedding scenario, we describe a linear-time algorithm for single-source digraphs, a quartic-time algorithm for series-parallel digraphs, and a fixed-parameter tractable algorithm for general digraphs. For the latter two classes, we make use of SPQR-trees and the notion of upward spirality. As an application of this drawing style, we show how to draw an upward planar phylogenetic network with two slopes such that all leaves lie on a horizontal line.

Let G=(V, E) be a planar graph and let V be a partition of V. We refer to the graphs induced by the vertex sets in V as clusters. Let DC be an arrangement of pairwise disjoint disks with a bijection between the disks and the clusters. Akitaya et al.[2] give an algorithm to test whether (G, V) can be embedded onto DC with the additional constraint that edges are routed through a set of pipes between the disks. If such an embedding exists, we prove that every clustered graph and every disk arrangement without pipe-disk intersections has a planar straight-line drawing where every vertex is embedded in the disk corresponding to its cluster. This result can be seen as an extension of the result by Alam et al.[3] who solely consider biconnected clusters. Moreover, we prove that it is NP-hard to decide whether a clustered graph has such a straight-line drawing, if we permit pipe-disk intersections, even if all disks have unit size. This answers an open question of Angelini et al.[4].