Search

Network visualization is one of the most widely used tools 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 present a mathematical and logical model of uncertainty as a range of values which can be used in network visualizations. We review some of the principles for visualizing uncertainty of different kinds, visual variables that can be used for representing uncertainty, and how these variables have been used to represent different data types in visualizations drawn from a range of non-humanities fields like climate science and bioinformatics. We then provide examples of two diagrams: one in which the variables displaying degrees of uncertainty are integrated into the graph and one in which glyphs are added to represent data certainty and uncertainty. Finally, we discuss how probabilistic data and what-if scenarios could be used to expand the representation of uncertainty in humanities network visualizations.

Network visualization is one of the most widely used tools 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 present a mathematical and logical model of uncertainty as a range of values which can be used in network visualizations. We review some of the principles for visualizing uncertainty of different kinds, visual variables that can be used for representing uncertainty, and how these variables have been used to represent different data types in visualizations drawn from a range of non-humanities fields like climate science and bioinformatics. We then provide examples of two diagrams: one in which the variables displaying degrees of uncertainty are integrated into the graph and one in which glyphs are added to represent data certainty and uncertainty. Finally, we discuss how probabilistic data and what-if scenarios could be used to expand the representation of uncertainty in humanities network visualizations.

Network visualization is one of the most widely used tools 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 present a mathematical and logical model of uncertainty as a range of values which can be used in network visualizations. We review some of the principles for visualizing uncertainty of different kinds, visual variables that can be used for representing uncertainty, and how these variables have been used to represent different data types in visualizations drawn from a range of non-humanities fields like climate science and bioinformatics. We then provide examples of two diagrams: one in which the variables displaying degrees of uncertainty are integrated into the graph and one in which glyphs are added to represent data certainty and uncertainty. Finally, we discuss how probabilistic data and what-if scenarios could be used to expand the representation of uncertainty in humanities network visualizations.

Network visualization is one of the most widely used tools 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 present a mathematical and logical model of uncertainty as a range of values which can be used in network visualizations. We review some of the principles for visualizing uncertainty of different kinds, visual variables that can be used for representing uncertainty, and how these variables have been used to represent different data types in visualizations drawn from a range of non-humanities fields like climate science and bioinformatics. We then provide examples of two diagrams: one in which the variables displaying degrees of uncertainty are integrated into the graph and one in which glyphs are added to represent data certainty and uncertainty. Finally, we discuss how probabilistic data and what-if scenarios could be used to expand the representation of uncertainty in humanities network visualizations.

Network visualization is one of the most widely used tools 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 present a mathematical and logical model of uncertainty as a range of values which can be used in network visualizations. We review some of the principles for visualizing uncertainty of different kinds, visual variables that can be used for representing uncertainty, and how these variables have been used to represent different data types in visualizations drawn from a range of non-humanities fields like climate science and bioinformatics. We then provide examples of two diagrams: one in which the variables displaying degrees of uncertainty are integrated into the graph and one in which glyphs are added to represent data certainty and uncertainty. Finally, we discuss how probabilistic data and what-if scenarios could be used to expand the representation of uncertainty in humanities network visualizations.

Network visualization is one of the most widely used tools 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 present a mathematical and logical model of uncertainty as a range of values which can be used in network visualizations. We review some of the principles for visualizing uncertainty of different kinds, visual variables that can be used for representing uncertainty, and how these variables have been used to represent different data types in visualizations drawn from a range of non-humanities fields like climate science and bioinformatics. We then provide examples of two diagrams: one in which the variables displaying degrees of uncertainty are integrated into the graph and one in which glyphs are added to represent data certainty and uncertainty. Finally, we discuss how probabilistic data and what-if scenarios could be used to expand the representation of uncertainty in humanities network visualizations., Funding: University of Memphis10.13039/100011518

Network visualization is one of the most widely used tools 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 present a mathematical and logical model of uncertainty as a range of values which can be used in network visualizations. We review some of the principles for visualizing uncertainty of different kinds, visual variables that can be used for representing uncertainty, and how these variables have been used to represent different data types in visualizations drawn from a range of non-humanities fields like climate science and bioinformatics. We then provide examples of two diagrams: one in which the variables displaying degrees of uncertainty are integrated/pinto the graph and one in which glyphs are added to represent data certainty and uncertainty. Finally, we discuss how probabilistic data and what-if scenarios could be used to expand the representation of uncertainty in humanities network visualizations.

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~$\mathcal{T}$ of a point set~$P$ in~$\mathbb{R}^2$ is a partitioning of the convex hull of~$P$ into pseudo-triangles, such that the union of the vertices of the pseudo-triangles is exactly~$P$. We call a size-4 pseudo-triangle a dart. For a fixed $k\geq 1$, we study $k$-dart pseudo-triangulations ($k$-DPTs), that is, pseudo-triangulations in which exactly $k$ 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 $1$-DPTs is generally not connected, and show how to compute its connected components. Furthermore, for $k$-DPTs on a point configuration called the double chain we analyze the structure of the flip graph on a more fine-grained level.

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 $n \geq 18$ 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$.

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.

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., Comment: Short paper for proceedings of EuroVis 2023 conference

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., Comment: Results from 2021

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.

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, i.e., 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 [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number k is NP-complete, for every k≥3 [SoCG 2019]. 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.

This report describes the 29th Annual Graph Drawing Contest, held in conjunction with the 30th International Symposium on Graph Drawing and Network Visualization (GD’22) in Tokyo, Japan. Due to the continuing global COVID-19 pandemic, the conference and thus also the contest was held in a hybrid format, with both on-site and online participants. The mission of the Graph Drawing Contest is to monitor and challenge the current state of the art in graph-drawing technology.

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.

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., Comment: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

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, i.e., 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 [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number $k$ is NP-complete, for every $k\geq 3$ [SoCG 2019]. 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., Comment: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

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 NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

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 N Phard 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]

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 UPSEs 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$ switches in its backbone admits an UPSE on every set of $n 2^{k-2}$ points., Comment: To appear at the 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021)

A mixed s-stack q-queue layout of a graph consists of a linear order of its vertices and of 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. Recently, Pupyrev disproved this conjectured by demonstrating a planar partial 3-tree that does not admit a 1-stack 1-queue layout. In this note, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees, also known as series-parallel graphs., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg [SIAM T. Discrete Math., 5 (1992), pp. 398-412] states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree has bounded queue number.

We study k-page upward book embeddings (kUBEs) of st-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on k pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a kUBE is NP-complete for k >= 3. A hardness result for this problem was previously known only for k = 6 [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on k=2. On the algorithmic side, we present polynomial-time algorithms for testing the existence of 2UBEs of planar st-graphs with branchwidth b and of plane st-graphs whose faces have a special structure. These algorithms run in O(f(b)* n+n^3) time and O(n) time, respectively, where f is a singly-exponential function on b. Moreover, on the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2UBE.

This report documents the program and the outcomes of Dagstuhl Seminar 18482 "Network Visualization in the Humanities", which took place November 26-30, 2019. The seminar brought together 27 researchers on Network Visualization and Digital Humanities communities. During the seminar the participants shared knowledge on the existing methods of network visualization and on network visualization challenges present in the Humanities through the introductory talks, the abstracts of which are included in this report. Multiple innovative research challenges for Network Visualisation in the Humanities have been identified and according to those four working groups have been set up that discussed the topics in detail. The summary of the discussions of the working groups is given in this report.

A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg [SIAM T. Discrete Math., 5 (1992), pp. 398-412] states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree has bounded queue number.

We study k-page upward book embeddings (kUBEs) of st-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on k pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a kUBE is NP-complete for k >= 3. A hardness result for this problem was previously known only for k = 6 [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on k=2. On the algorithmic side, we present polynomial-time algorithms for testing the existence of 2UBEs of planar st-graphs with branchwidth b and of plane st-graphs whose faces have a special structure. These algorithms run in O(f(b)* n+n^3) time and O(n) time, respectively, where f is a singly-exponential function on b. Moreover, on the combinatorial side, we present two notable families of plane st-graphs that always admit an embedding-preserving 2UBE.

This report documents the program and the outcomes of Dagstuhl Seminar 18482 "Network Visualization in the Humanities", which took place November 26-30, 2019. The seminar brought together 27 researchers on Network Visualization and Digital Humanities communities. During the seminar the participants shared knowledge on the existing methods of network visualization and on network visualization challenges present in the Humanities through the introductory talks, the abstracts of which are included in this report. Multiple innovative research challenges for Network Visualisation in the Humanities have been identified and according to those four working groups have been set up that discussed the topics in detail. The summary of the discussions of the working groups is given in this report.

We introduce and study level-planar straight-line drawings with a fixed number $\lambda$ of slopes. For proper level graphs, we give an $O(n \log^2 n / \log \log n)$-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 $O(n^{4/3} \log n)$-time and $O({\lambda} n^{10/3} \log n)$-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 $\lambda$ slopes is $\textsf{NP}$-hard even in restricted cases., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

The visual complexity of a graph drawing can be measured by the number of geometric objects used for the representation of its elements. In this paper, we study planar graph drawings where edges are represented by few segments. In such a drawing, one segment may represent multiple edges forming a path. Drawings of planar graphs with few segments were intensively studied in the past years. However, the area requirements were only considered for limited subclasses of planar graphs. In this paper, we show that trees have drawings with $3n/4-1$ segments and $n^2$ area, improving the previous result of $O(n^{3.58})$. We also show that 3-connected planar graphs and biconnected outerplanar graphs have a drawing with $8n/3-O(1)$ and $3n/2-O(1)$ segments, respectively, and $O(n^3)$ area., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

We study $k$-page upward book embeddings ($k$UBEs) of $st$-graphs, that is, book embeddings of single-source single-sink directed acyclic graphs on $k$ pages with the additional requirement that the vertices of the graph appear in a topological ordering along the spine of the book. We show that testing whether a graph admits a $k$UBE is NP-complete for $k\geq 3$. A hardness result for this problem was previously known only for $k = 6$ [Heath and Pemmaraju, 1999]. Motivated by this negative result, we focus our attention on $k=2$. On the algorithmic side, we present polynomial-time algorithms for testing the existence of $2$UBEs of planar $st$-graphs with branchwidth $\beta$ and of plane $st$-graphs whose faces have a special structure. These algorithms run in $O(f(\beta)\cdot n+n^3)$ time and $O(n)$ time, respectively, where $f$ is a singly-exponential function on $\beta$. Moreover, on the combinatorial side, we present two notable families of plane $st$-graphs that always admit an embedding-preserving $2$UBE., Comment: Extended version of "Upward Book Embeddings of st-Graphs", to appear in Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019)

Let $G=(V, E)$ be a planar graph and let $\mathcal{C}$ be a partition of $V$. We refer to the graphs induced by the vertex sets in $\mathcal{C}$ as Clusters. Let $D_{\mathcal C}$ be an arrangement of disks with a bijection between the disks and the clusters. Akitaya et al. give an algorithm to test whether $(G, \mathcal{C})$ can be embedded onto $D_{\mathcal C}$ with the additional constraint that edges are routed through a set of pipes between the disks. Based on such an embedding, 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. 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., Comment: Preliminary work appeared in the Proceedings of the 13th International Conference and Workshops on Algorithms and Computation (WALCOM 2019)

A \emph{queue layout} of a graph consists of a \emph{linear order} of its vertices and a partition of its edges into \emph{queues}, so that no two independent edges of the same queue are nested. The \emph{queue number} of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every $k$-planar graph (i.e., every graph that can be drawn in the plane with at most $k$ crossings per edge) of bounded degree has bounded queue number.

The crossing angle of a straight-line drawing $\Gamma$ of a graph $G=(V, E)$ is the smallest angle between two crossing edges in $\Gamma$. Deciding whether a graph $G$ has a straight-line drawing with a crossing angle of $90^\circ$ is $\mathcal NP$-hard. We propose a simple heuristic to compute a drawing with a large crossing angle. The heuristic greedily selects the best position for a single vertex in a random set of points. The algorithm is accompanied by a speed-up technique to compute the crossing angle of a straight-line drawing. We show the effectiveness of the heuristic in an extensive empirical evaluation. Our heuristic was clearly the winning algorithm (CoffeeVM) in the Graph Drawing Challenge 2017., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

This paper addresses the following basic question: given two layouts of the same graph, which one is more aesthetically pleasing? We propose a neural network-based discriminator model trained on a labeled dataset that decides which of two layouts has a higher aesthetic quality. The feature vectors used as inputs to the model are based on known graph drawing quality metrics, classical statistics, information-theoretical quantities, and two-point statistics inspired by methods of condensed matter physics. The large corpus of layout pairs used for training and testing is constructed using force-directed drawing algorithms and the layouts that naturally stem from the process of graph generation. It is further extended using data augmentation techniques. The mean prediction accuracy of our model is 95.70%, outperforming discriminators based on stress and on the linear combination of popular quality metrics by a statistically significant margin., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

A drawing of a graph is greedy if for each ordered pair of vertices u and v, there is a path from u to v such that the Euclidean distance to v decreases monotonically at every vertex of the path. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings, in which each edge is either a horizontal or a vertical segment. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation, i.e., a plane graph with specified vertex angles, admits vertex coordinates that define a greedy drawing. We provide a characterization, a linear-time testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i.e., those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomial-time testing and drawing algorithm for a meaningful subset of instances., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

We consider the problem of extending the drawing of a subgraph of a given plane graph to a drawing of the entire graph using straight-line and polyline edges. We define the notion of star complexity of a polygon and show that a drawing $\Gamma_H$ of an induced connected subgraph $H$ can be extended with at most $\min\{ h/2, \beta + \log_2(h) + 1\}$ bends per edge, where $\beta$ is the largest star complexity of a face of $\Gamma_H$ and $h$ is the size of the largest face of $H$. This result significantly improves the previously known upper bound of $72|V(H)|$ [5] for the case where $H$ is connected. We also show that our bound is worst case optimal up to a small additive constant. Additionally, we provide an indication of complexity of the problem of testing whether a star-shaped inner face can be extended to a straight-line drawing of the graph; this is in contrast to the fact that the same problem is solvable in linear time for the case of star-shaped outer face [9] and convex inner face [13]., Comment: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)

A $k$-page book drawing of a graph $G=(V,E)$ consists of a linear ordering of its vertices along a spine and an assignment of each edge to one of the $k$ pages, which are half-planes bounded by the spine. In a book drawing, two edges cross if and only if they are assigned to the same page and their vertices alternate along the spine. Crossing minimization in a $k$-page book drawing is NP-hard, yet book drawings have multiple applications in visualization and beyond. Therefore several heuristic book drawing algorithms exist, but there is no broader comparative study on their relative performance. In this paper, we propose a comprehensive benchmark set of challenging graph classes for book drawing algorithms and provide an extensive experimental study of the performance of existing book drawing algorithms., Comment: Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

A fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other part, together with the edges, must be added to the drawing. We assume that G is planar and study the problem of finding, for a given k >= 0, a planar poly-line drawing of G with at most k bends per edge. In the most general case, we show NP-hardness. For k=0 and under additional constraints on the positions of the fixed or mobile vertices, we either prove that the problem is polynomial-time solvable or prove that it belongs to NP. Finally, we present a polynomial-time testing algorithm for a certain type of "layered" 1-bend drawings.