Showing 1–50 of 109 results for author: Kobourov, S

Wooly Graphs : A Mathematical Framework For Knitting

Authors: Kathryn Gray, Brian Bell, Diana Sieper, Stephen Kobourov, Falk Schreiber, Karsten Klein, Seokhee Hong

Abstract: This paper aims to develop a mathematical foundation to model knitting with graphs. We provide a precise definition for knit objects with a knot theoretic component and propose a simple undirected graph, a simple directed graph, and a directed multigraph model for any arbitrary knit object. Using these models, we propose natural categories related to the complexity of knitting structures. We use t… ▽ More This paper aims to develop a mathematical foundation to model knitting with graphs. We provide a precise definition for knit objects with a knot theoretic component and propose a simple undirected graph, a simple directed graph, and a directed multigraph model for any arbitrary knit object. Using these models, we propose natural categories related to the complexity of knitting structures. We use these categories to explore the hardness of determining whether a knit object of each class exists for a given graph. We show that while this problem is NP-hard in general, under specific cases, there are linear and polynomial time algorithms which take advantage of unique properties of common knitting techniques. This work aims to bridge the gap between textile arts and graph theory, offering a useful and rigorous framework for analyzing knitting objects using their corresponding graphs and for generating knitting objects from graphs. △ Less

Submitted 3 July, 2024; v1 submitted 29 June, 2024; originally announced July 2024.

Comments: 11 pages, 4 tables, 5 figures

A Graph Model and a Layout Algorithm for Knitting Patterns

Authors: Kathryn Gray, Brian Bell, Stephen Kobourov

Abstract: Knitting, an ancient fiber art, creates a structured fabric consisting of loops or stitches. Publishing hand knitting patterns involves lengthy testing periods and numerous knitters. Modeling knitting patterns with graphs can help expedite error detection and pattern validation. In this paper, we describe how to model simple knitting patterns as planar graphs. We then design, implement, and evalua… ▽ More Knitting, an ancient fiber art, creates a structured fabric consisting of loops or stitches. Publishing hand knitting patterns involves lengthy testing periods and numerous knitters. Modeling knitting patterns with graphs can help expedite error detection and pattern validation. In this paper, we describe how to model simple knitting patterns as planar graphs. We then design, implement, and evaluate a layout algorithm to visualize knitting patterns. Knitting patterns correspond to graphs with pre-specified edge lengths (e.g., uniform lengths, two lengths, etc.). This yields a natural graph layout optimization problem: realize a planar graph with pre-specified edge lengths, while ensuring there are no edge crossings. We quantitatively evaluate our algorithm using real knitting patterns of various sizes against three others; one created for knitting patterns, one that maintains planarity and optimizes edge lengths, and a popular force-directed algorithm. △ Less

Submitted 19 June, 2024; originally announced June 2024.

Comments: 13 pages, 6 tables, 7 figures

Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search

Authors: Alvin Chiu, Mithun Ghosh, Reyan Ahmed, Kwang-Sung Jun, Stephen Kobourov, Michael T. Goodrich

Abstract: Graph neural networks have been successful for machine learning, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing graph sparsifiers by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes… ▽ More Graph neural networks have been successful for machine learning, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing graph sparsifiers by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a sparsifier. The proposed method consistently outperforms several standard approximation algorithms on different types of graphs and often finds the optimal solution. △ Less

Submitted 16 November, 2023; originally announced November 2023.

Comments: arXiv admin note: substantial text overlap with arXiv:2305.00535

Balancing between the Local and Global Structures (LGS) in Graph Embedding

Authors: Jacob Miller, Vahan Huroyan, Stephen Kobourov

Abstract: We present a method for balancing between the Local and Global Structures (LGS) in graph embedding, via a tunable parameter. Some embedding methods aim to capture global structures, while others attempt to preserve local neighborhoods. Few methods attempt to do both, and it is not always possible to capture well both local and global information in two dimensions, which is where most graph drawing… ▽ More We present a method for balancing between the Local and Global Structures (LGS) in graph embedding, via a tunable parameter. Some embedding methods aim to capture global structures, while others attempt to preserve local neighborhoods. Few methods attempt to do both, and it is not always possible to capture well both local and global information in two dimensions, which is where most graph drawing live. The choice of using a local or a global embedding for visualization depends not only on the task but also on the structure of the underlying data, which may not be known in advance. For a given graph, LGS aims to find a good balance between the local and global structure to preserve. We evaluate the performance of LGS with synthetic and real-world datasets and our results indicate that it is competitive with the state-of-the-art methods, using established quality metrics such as stress and neighborhood preservation. We introduce a novel quality metric, cluster distance preservation, to assess intermediate structure capture. All source-code, datasets, experiments and analysis are available online. △ Less

Submitted 1 September, 2023; v1 submitted 30 August, 2023; originally announced August 2023.

Comments: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

Parameterized and Approximation Algorithms for the Maximum Bimodal Subgraph Problem

Authors: Walter Didimo, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Stephen Kobourov, Marie Diana Sieper

Abstract: A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) proble… ▽ More A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an FPT algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS. △ Less

Submitted 29 August, 2023; originally announced August 2023.

Comments: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

2D, 2.5D, or 3D? An Exploratory Study on Multilayer Network Visualisations in Virtual Reality

Authors: Stefan P. Feyer, Bruno Pinaud, Stephen G. Kobourov, Nicolas Brich, Michael Krone, Andreas Kerren, Michael Behrisch, Falk Schreiber, Karsten Klein

Abstract: Relational information between different types of entities is often modelled by a multilayer network (MLN) -- a network with subnetworks represented by layers. The layers of an MLN can be arranged in different ways in a visual representation, however, the impact of the arrangement on the readability of the network is an open question. Therefore, we studied this impact for several commonly occu… ▽ More Relational information between different types of entities is often modelled by a multilayer network (MLN) -- a network with subnetworks represented by layers. The layers of an MLN can be arranged in different ways in a visual representation, however, the impact of the arrangement on the readability of the network is an open question. Therefore, we studied this impact for several commonly occurring tasks related to MLN analysis. Additionally, layer arrangements with a dimensionality beyond 2D, which are common in this scenario, motivate the use of stereoscopic displays. We ran a human subject study utilising a Virtual Reality headset to evaluate 2D, 2.5D, and 3D layer arrangements. The study employs six analysis tasks that cover the spectrum of an MLN task taxonomy, from path finding and pattern identification to comparisons between and across layers. We found no clear overall winner. However, we explore the task-to-arrangement space and derive empirical-based recommendations on the effective use of 2D, 2.5D, and 3D layer arrangements for MLNs. △ Less

Submitted 13 September, 2023; v1 submitted 20 July, 2023; originally announced July 2023.

Journal ref: IEEE Transactions on Visualization and Computer Graphics, In press, To appear. Accepted to IEEE VIS 2023

A Scalable Method for Readable Tree Layouts

Authors: Kathryn Gray, Mingwei Li, Reyan Ahmed, Md. Khaledur Rahman, Ariful Azad, Stephen Kobourov, Katy Börner

Abstract: Large tree structures are ubiquitous and real-world relational datasets often have information associated with nodes (e.g., labels or other attributes) and edges (e.g., weights or distances) that need to be communicated to the viewers. Yet, scalable, easy to read tree layouts are difficult to achieve. We consider tree layouts to be readable if they meet some basic requirements: node labels should… ▽ More Large tree structures are ubiquitous and real-world relational datasets often have information associated with nodes (e.g., labels or other attributes) and edges (e.g., weights or distances) that need to be communicated to the viewers. Yet, scalable, easy to read tree layouts are difficult to achieve. We consider tree layouts to be readable if they meet some basic requirements: node labels should not overlap, edges should not cross, edge lengths should be preserved, and the output should be compact. There are many algorithms for drawing trees, although very few take node labels or edge lengths into account, and none optimizes all requirements above. With this in mind, we propose a new scalable method for readable tree layouts. The algorithm guarantees that the layout has no edge crossings and no label overlaps, and optimizes one of the remaining aspects: desired edge lengths and compactness. We evaluate the performance of the new algorithm by comparison with related earlier approaches using several real-world datasets, ranging from a few thousand nodes to hundreds of thousands of nodes. Tree layout algorithms can be used to visualize large general graphs, by extracting a hierarchy of progressively larger trees. We illustrate this functionality by presenting several map-like visualizations generated by the new tree layout algorithm. △ Less

Submitted 16 May, 2023; originally announced May 2023.

Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search

Authors: Reyan Ahmed, Mithun Ghosh, Kwang-Sung Jun, Stephen Kobourov

Abstract: Graph neural networks are useful for learning problems, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing Steiner Trees by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node t… ▽ More Graph neural networks are useful for learning problems, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing Steiner Trees by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a Steiner tree. The proposed method consistently outperforms the standard 2-approximation algorithm on many different types of graphs and often finds the optimal solution. △ Less

Submitted 30 April, 2023; originally announced May 2023.

Simultaneous Drawing of Layered Trees

Authors: Julia Katheder, Stephen G. Kobourov, Axel Kuckuk, Maximilian Pfister, Johannes Zink

Abstract: We study the crossing-minimization problem in a layered graph drawing of planar-embedded rooted trees whose leaves have a given total order on the first layer, which adheres to the embedding of each individual tree. The task is then to permute the vertices on the other layers (respecting the given tree embeddings) in order to minimize the number of crossings. While this problem is known to be NP-h… ▽ More We study the crossing-minimization problem in a layered graph drawing of planar-embedded rooted trees whose leaves have a given total order on the first layer, which adheres to the embedding of each individual tree. The task is then to permute the vertices on the other layers (respecting the given tree embeddings) in order to minimize the number of crossings. While this problem is known to be NP-hard for multiple trees even on just two layers, we describe a dynamic program running in polynomial time for the restricted case of two trees. If there are more than two trees, we restrict the number of layers to three, which allows for a reduction to a shortest-path problem. This way, we achieve XP-time in the number of trees. △ Less

Submitted 28 February, 2024; v1 submitted 23 February, 2023; originally announced February 2023.

Comments: Appears in Proc. 18th International Conference and Workshops on Algorithms and Computation 2024 (WALCOM'24)

Multi-Priority Graph Sparsification

Authors: Reyan Ahmed, Keaton Hamm, Stephen Kobourov, Mohammad Javad Latifi Jebelli, Faryad Darabi Sahneh, Richard Spence

Abstract: A \emph{sparsification} of a given graph $G$ is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of $G$. Examples of sparsifications include but are not limited to spanning trees, Steiner trees, spanners, emulators, and distance preservers. Each vertex has the same priority in all of these problems. However, real-world graphs typically assign different ``p… ▽ More A \emph{sparsification} of a given graph $G$ is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of $G$. Examples of sparsifications include but are not limited to spanning trees, Steiner trees, spanners, emulators, and distance preservers. Each vertex has the same priority in all of these problems. However, real-world graphs typically assign different ``priorities'' or ``levels'' to different vertices, in which higher-priority vertices require higher-quality connectivity between them. Multi-priority variants of the Steiner tree problem have been studied in prior literature but this generalization is much less studied for other sparsification problems. In this paper, we define a generalized multi-priority problem and present a rounding-up approach that can be used for a variety of graph sparsifications. Our analysis provides a systematic way to compute approximate solutions to multi-priority variants of a wide range of graph sparsification problems given access to a single-priority subroutine. △ Less

Submitted 29 January, 2023; originally announced January 2023.

Splitting Vertices in 2-Layer Graph Drawings

Authors: Reyan Ahmed, Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Michael Kaufmann, Philipp Kindermann, Stephen Kobourov, Martin Nöllenburg, Antonios Symvonis, Anaïs Villedieu, Markus Wallinger

Abstract: Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two sets of entities (vertices) are placed on two parallel lines (layers), and their relationships (edges) are represented by segments connecting vertices. Methods for constructing 2-layer drawings often try to minimize the… ▽ More Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two sets of entities (vertices) are placed on two parallel lines (layers), and their relationships (edges) are represented by segments connecting vertices. Methods for constructing 2-layer drawings often try to minimize the number of edge crossings. We use vertex splitting to reduce the number of crossings, by replacing selected vertices on one layer by two (or more) copies and suitably distributing their incident edges among these copies. We study several optimization problems related to vertex splitting, either minimizing the number of crossings or removing all crossings with fewest splits. While we prove that some variants are \NP-complete, we obtain polynomial-time algorithms for others. We run our algorithms on a benchmark set of bipartite graphs representing the relationships between human anatomical structures and cell types. △ Less

Submitted 15 April, 2023; v1 submitted 25 January, 2023; originally announced January 2023.

The Rique-Number of Graphs

Authors: Michael A. Bekos, Stefan Felsner, Philipp Kindermann, Stephen Kobourov, Jan Kratovíl, Ignaz Rutter

Abstract: We continue the study of linear layouts of graphs in relation to known data structures. At a high level, given a data structure, the goal is to find a linear order of the vertices of the graph and a partition of its edges into pages, such that the edges in each page follow the restriction of the given data structure in the underlying order. In this regard, the most notable representatives are the… ▽ More We continue the study of linear layouts of graphs in relation to known data structures. At a high level, given a data structure, the goal is to find a linear order of the vertices of the graph and a partition of its edges into pages, such that the edges in each page follow the restriction of the given data structure in the underlying order. In this regard, the most notable representatives are the stack and queue layouts, while there exists some work also for deques. In this paper, we study linear layouts of graphs that follow the restriction of a restricted-input queue (rique), in which insertions occur only at the head, and removals occur both at the head and the tail. We characterize the graphs admitting rique layouts with a single page and we use the characterization to derive a corresponding testing algorithm when the input graph is maximal planar. We finally give bounds on the number of needed pages (so-called rique-number) of complete graphs. △ Less

Submitted 1 September, 2022; originally announced September 2022.

Comments: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

Spherical Graph Drawing by Multi-dimensional Scaling

Authors: Jacob Miller, Vahan Huroyan, Stephen Kobourov

Abstract: We describe an efficient and scalable spherical graph embedding method. The method uses a generalization of the Euclidean stress function for Multi-Dimensional Scaling adapted to spherical space, where geodesic pairwise distances are employed instead of Euclidean distances. The resulting spherical stress function is optimized by means of stochastic gradient descent. Quantitative and qualitative ev… ▽ More We describe an efficient and scalable spherical graph embedding method. The method uses a generalization of the Euclidean stress function for Multi-Dimensional Scaling adapted to spherical space, where geodesic pairwise distances are employed instead of Euclidean distances. The resulting spherical stress function is optimized by means of stochastic gradient descent. Quantitative and qualitative evaluations demonstrate the scalability and effectiveness of the proposed method. We also show that some graph families can be embedded with lower distortion on the sphere, than in Euclidean and hyperbolic spaces. △ Less

Submitted 31 August, 2022; originally announced September 2022.

Comments: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

An FPT Algorithm for Bipartite Vertex Splitting

Authors: Reyan Ahmed, Stephen Kobourov, Myroslav Kryven

Abstract: Bipartite graphs model the relationship between two disjoint sets of objects. They have a wide range of applications and are often visualized as a 2-layered drawing, where each set of objects is visualized as a set of vertices (points) on one of the two parallel horizontal lines and the relationships are represented by edges (simple curves) between the two lines connecting the corresponding vertic… ▽ More Bipartite graphs model the relationship between two disjoint sets of objects. They have a wide range of applications and are often visualized as a 2-layered drawing, where each set of objects is visualized as a set of vertices (points) on one of the two parallel horizontal lines and the relationships are represented by edges (simple curves) between the two lines connecting the corresponding vertices. One of the common objectives in such drawings is to minimize the number of crossings this, however, is computationally expensive and may still result in drawings with so many crossings that they affect the readability of the drawing. We consider a recent approach to remove crossings in such visualizations by splitting vertices, where the goal is to find the minimum number of vertices to be split to obtain a planar drawing. We show that determining whether a planar drawing exists after splitting at most $k$ vertices is fixed parameter tractable in $k$. △ Less

Submitted 26 August, 2022; originally announced August 2022.

Comments: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

ENS-t-SNE: Embedding Neighborhoods Simultaneously t-SNE

Authors: Jacob Miller, Vahan Huroyan, Raymundo Navarrete, Md Iqbal Hossain, Stephen Kobourov

Abstract: When visualizing a high-dimensional dataset, dimension reduction techniques are commonly employed which provide a single 2-dimensional view of the data. We describe ENS-t-SNE: an algorithm for Embedding Neighborhoods Simultaneously that generalizes the t-Stochastic Neighborhood Embedding approach. By using different viewpoints in ENS-t-SNE's 3D embedding, one can visualize different types of clust… ▽ More When visualizing a high-dimensional dataset, dimension reduction techniques are commonly employed which provide a single 2-dimensional view of the data. We describe ENS-t-SNE: an algorithm for Embedding Neighborhoods Simultaneously that generalizes the t-Stochastic Neighborhood Embedding approach. By using different viewpoints in ENS-t-SNE's 3D embedding, one can visualize different types of clusters within the same high-dimensional dataset. This enables the viewer to see and keep track of the different types of clusters, which is harder to do when providing multiple 2D embeddings, where corresponding points cannot be easily identified. We illustrate the utility of ENS-t-SNE with real-world applications and provide an extensive quantitative evaluation with datasets of different types and sizes. △ Less

Submitted 30 March, 2024; v1 submitted 23 May, 2022; originally announced May 2022.

Browser-based Hyperbolic Visualization of Graphs

Authors: Jacob Miller, Stephen Kobourov, Vahan Huroyan

Abstract: Hyperbolic geometry offers a natural focus + context for data visualization and has been shown to underlie real-world complex networks. However, current hyperbolic network visualization approaches are limited to special types of networks and do not scale to large datasets. With this in mind, we designed, implemented, and analyzed three methods for hyperbolic visualization of networks in the browse… ▽ More Hyperbolic geometry offers a natural focus + context for data visualization and has been shown to underlie real-world complex networks. However, current hyperbolic network visualization approaches are limited to special types of networks and do not scale to large datasets. With this in mind, we designed, implemented, and analyzed three methods for hyperbolic visualization of networks in the browser based on inverse projections, generalized force-directed algorithms, and hyperbolic multi-dimensional scaling (H-MDS). A comparison with Euclidean MDS shows that H-MDS produces embeddings with lower distortion for several types of networks. All three methods can handle node-link representations and are available in fully functional web-based systems. △ Less

Submitted 16 May, 2022; originally announced May 2022.

Comments: To appear in IEEE PacificVis 2022

The Influence of Dimensions on the Complexity of Computing Decision Trees

Authors: Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms

Abstract: A decision tree recursively splits a feature space $\mathbb{R}^{d}$ and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, littl… ▽ More A decision tree recursively splits a feature space $\mathbb{R}^{d}$ and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number $d$ of dimensions of the feature space. We show that it can be solved in $O(n^{2d + 1}d)$ time, but under reasonable complexity-theoretic assumptions it is not possible to achieve $f(d) \cdot n^{o(d / \log d)}$ running time, where $n$ is the number of training examples. The problem is solvable in $(dR)^{O(dR)} \cdot n^{1+o(1)}$ time, if there are exactly two classes and $R$ is an upper bound on the number of tree leaves labeled with the first~class. △ Less

Submitted 2 June, 2022; v1 submitted 16 May, 2022; originally announced May 2022.

Comments: 13 pages, 8 figures

The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs

Authors: Ina Goeßmann, Jonathan Klawitter, Boris Klemz, Felix Klesen, Stephen Kobourov, Myroslav Kryven, Alexander Wolff, Johannes Zink

Abstract: The segment number of a planar graph $G$ is the smallest number of line segments needed for a planar straight-line drawing of $G$. Dujmović, Eppstein, Suderman, and Wood [CGTA'07] introduced this measure for the visual complexity of graphs. There are optimal algorithms for trees and worst-case optimal algorithms for outerplanar graphs, 2-trees, and planar 3-trees. It is known that every cubic tric… ▽ More The segment number of a planar graph $G$ is the smallest number of line segments needed for a planar straight-line drawing of $G$. Dujmović, Eppstein, Suderman, and Wood [CGTA'07] introduced this measure for the visual complexity of graphs. There are optimal algorithms for trees and worst-case optimal algorithms for outerplanar graphs, 2-trees, and planar 3-trees. It is known that every cubic triconnected planar $n$-vertex graph (except $K_4$) has segment number $n/2+3$, which is the only known universal lower bound for a meaningful class of planar graphs. We show that every triconnected planar 4-regular graph can be drawn using at most $n+3$ segments. This bound is tight up to an additive constant, improves a previous upper bound of $7n/4+2$ implied by a more general result of Dujmović et al., and supplements the result for cubic graphs. We also give a simple optimal algorithm for cactus graphs, generalizing the above-mentioned result for trees. We prove the first linear universal lower bounds for outerpaths, maximal outerplanar graphs, 2-trees, and planar 3-trees. This shows that the existing algorithms for these graph classes are constant-factor approximations. For maximal outerpaths, our bound is best possible and can be generalized to circular arcs. △ Less

Submitted 15 July, 2022; v1 submitted 23 February, 2022; originally announced February 2022.

Comments: Appears in the Proceedings of the 48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2022)

Multicriteria Scalable Graph Drawing via Stochastic Gradient Descent, $(SGD)^2$

Authors: Reyan Ahmed, Felice De Luca, Sabin Devkota, Stephen Kobourov, Mingwei Li

Abstract: Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Multicriteria Scalable Graph Drawing via Stochastic Gradient Descen… ▽ More Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Multicriteria Scalable Graph Drawing via Stochastic Gradient Descent, $(SGD)^2$, that can handle multiple readability criteria. $(SGD)^2$ can optimize any criterion that can be described by a differentiable function. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., node resolution, angular resolution, aspect ratio). The approach is scalable and can handle large graphs. A variation of the underlying approach can also be used to optimize many desirable properties in planar graphs, while maintaining planarity. Finally, we provide quantitative and qualitative evidence of the effectiveness of $(SGD)^2$: we analyze the interactions between criteria, measure the quality of layouts generated from $(SGD)^2$ as well as the runtime behavior, and analyze the impact of sample sizes. The source code is available on github and we also provide an interactive demo for small graphs. △ Less

Submitted 2 December, 2021; originally announced December 2021.

Comments: arXiv admin note: text overlap with arXiv:2008.05584

Approximation algorithms for priority Steiner tree problems

Authors: Faryad Darabi Sahneh, Stephen Kobourov, Richard Spence

Abstract: In the Priority Steiner Tree (PST) problem, we are given an undirected graph $G=(V,E)$ with a source $s \in V$ and terminals $T \subseteq V \setminus \{s\}$, where each terminal $v \in T$ requires a nonnegative priority $P(v)$. The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from $s$ to each terminal $v$ consists of edges of rate greater th… ▽ More In the Priority Steiner Tree (PST) problem, we are given an undirected graph $G=(V,E)$ with a source $s \in V$ and terminals $T \subseteq V \setminus \{s\}$, where each terminal $v \in T$ requires a nonnegative priority $P(v)$. The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from $s$ to each terminal $v$ consists of edges of rate greater than or equal to $P(v)$. The PST problem with $k$ priorities admits a $\min\{2 \ln |T| + 2, kρ\}$-approximation [Charikar et al., 2004], and is hard to approximate with ratio $c \log \log n$ for some constant $c$ [Chuzhoy et al., 2008]. In this paper, we first strengthen the analysis provided by [Charikar et al., 2004] for the $(2 \ln |T| + 2)$-approximation to show an approximation ratio of $\lceil \log_2 |T| \rceil + 1 \le 1.443 \ln |T| + 2$, then provide a very simple, parallelizable algorithm which achieves the same approximation ratio. We then consider a more difficult node-weighted version of the PST problem, and provide a $(2 \ln |T|+2)$-approximation using extensions of the spider decomposition by [Klein \& Ravi, 1995]. This is the first result for the PST problem in node-weighted graphs. Moreover, the approximation ratios for all above algorithms are tight. △ Less

Submitted 30 August, 2021; originally announced August 2021.

Visualizing JIT Compiler Graphs

Authors: HeuiChan Lim, Stephen Kobourov

Abstract: Just-in-time (JIT) compilers are used by many modern programming systems in order to improve performance. Bugs in JIT compilers provide exploitable security vulnerabilities and debugging them is difficult as they are large, complex, and dynamic. Current debugging and visualization tools deal with static code and are not suitable in this domain. We describe a new approach for simplifying the large… ▽ More Just-in-time (JIT) compilers are used by many modern programming systems in order to improve performance. Bugs in JIT compilers provide exploitable security vulnerabilities and debugging them is difficult as they are large, complex, and dynamic. Current debugging and visualization tools deal with static code and are not suitable in this domain. We describe a new approach for simplifying the large and complex intermediate representation, generated by a JIT compiler and visualize it with a metro map metaphor to aid developers in debugging. △ Less

Submitted 25 August, 2021; originally announced August 2021.

Comments: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021). arXiv admin note: substantial text overlap with arXiv:2107.00063

Computing Steiner Trees using Graph Neural Networks

Authors: Reyan Ahmed, Md Asadullah Turja, Faryad Darabi Sahneh, Mithun Ghosh, Keaton Hamm, Stephen Kobourov

Abstract: Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problems such as subgraph isomorphism, detecting cliques, and the traveling salesman problem. However, many NP-complete problems are as of yet unexplored using this method. In this paper,… ▽ More Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problems such as subgraph isomorphism, detecting cliques, and the traveling salesman problem. However, many NP-complete problems are as of yet unexplored using this method. In this paper, we tackle the Steiner Tree Problem. We employ four learning frameworks to compute low cost Steiner trees: feed-forward neural networks, graph neural networks, graph convolutional networks, and a graph attention model. We use these frameworks in two fundamentally different ways: 1) to train the models to learn the actual Steiner tree nodes, 2) to train the model to learn good Steiner point candidates to be connected to the constructed tree using a shortest path in a greedy fashion. We illustrate the robustness of our heuristics on several random graph generation models as well as the SteinLib data library. Our finding suggests that the out-of-the-box application of GNN methods does worse than the classic 2-approximation method. However, when combined with a greedy shortest path construction, it even does slightly better than the 2-approximation algorithm. This result sheds light on the fundamental capabilities and limitations of graph learning techniques on classical NP-complete problems. △ Less

Submitted 18 August, 2021; originally announced August 2021.

Visualizing The Intermediate Representation of Just-in-Time Compilers

Authors: HeuiChan Lim, Stephen Kobourov

Abstract: Just-in-Time (JIT) compilers are used by many modern programming systems in order to improve performance. Bugs in JIT compilers provide exploitable security vulnerabilities and debugging them is difficult as they are large, complex, and dynamic. Current debugging and visualization tools deal with static code and are not suitable in this domain. We describe a new approach for simplifying the large… ▽ More Just-in-Time (JIT) compilers are used by many modern programming systems in order to improve performance. Bugs in JIT compilers provide exploitable security vulnerabilities and debugging them is difficult as they are large, complex, and dynamic. Current debugging and visualization tools deal with static code and are not suitable in this domain. We describe a new approach for simplifying the large and complex intermediate representation, generated by a JIT compiler and visualize it with a metro map metaphor to aid developers in debugging. Experiments using our prototype implementation on Google's V8 JavaScript interpreter and TurboFan JIT compiler demonstrate that it can help identify and localize buggy code. △ Less

Submitted 9 June, 2021; originally announced July 2021.

Comments: 24 pages

Visualizing Evolving Trees

Authors: Kathryn Gray, Mingwei Li, Reyan Ahmed, Stephen Kobourov

Abstract: Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge… ▽ More Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge crossings. With this in mind we propose two methods for visualizing evolving trees that guarantee no edge crossings, while optimizing (1) desired edge length realization, (2) layout compactness, and (3) stability. We evaluate the two new methods, along with five prior approaches (three static and two dynamic), on real-world datasets using quantitative metrics: stress, desired edge length realization, layout compactness, stability, and running time. The new methods are fully functional and available on github. △ Less

Submitted 26 August, 2022; v1 submitted 16 June, 2021; originally announced June 2021.

Comments: Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

On additive spanners in weighted graphs with local error

Authors: Reyan Ahmed, Greg Bodwin, Keaton Hamm, Stephen Kobourov, Richard Spence

Abstract: An \emph{additive $+β$ spanner} of a graph $G$ is a subgraph which preserves distances up to an additive $+β$ error. Additive spanners are well-studied in unweighted graphs but have only recently received attention in weighted graphs [Elkin et al.\ 2019 and 2020, Ahmed et al.\ 2020]. This paper makes two new contributions to the theory of weighted additive spanners. For weighted graphs, [Ahmed e… ▽ More An \emph{additive $+β$ spanner} of a graph $G$ is a subgraph which preserves distances up to an additive $+β$ error. Additive spanners are well-studied in unweighted graphs but have only recently received attention in weighted graphs [Elkin et al.\ 2019 and 2020, Ahmed et al.\ 2020]. This paper makes two new contributions to the theory of weighted additive spanners. For weighted graphs, [Ahmed et al.\ 2020] provided constructions of sparse spanners with \emph{global} error $β= cW$, where $W$ is the maximum edge weight in $G$ and $c$ is constant. We improve these to \emph{local} error by giving spanners with additive error $+cW(s,t)$ for each vertex pair $(s,t)$, where $W(s, t)$ is the maximum edge weight along the shortest $s$--$t$ path in $G$. These include pairwise $+(2+\eps)W(\cdot,\cdot)$ and $+(6+\eps) W(\cdot, \cdot)$ spanners over vertex pairs $\Pc \subseteq V \times V$ on $O_{\eps}(n|\Pc|^{1/3})$ and $O_{\eps}(n|\Pc|^{1/4})$ edges for all $\eps > 0$, which extend previously known unweighted results up to $\eps$ dependence, as well as an all-pairs $+4W(\cdot,\cdot)$ spanner on $\widetilde{O}(n^{7/5})$ edges. Besides sparsity, another natural way to measure the quality of a spanner in weighted graphs is by its \emph{lightness}, defined as the total edge weight of the spanner divided by the weight of an MST of $G$. We provide a $+\eps W(\cdot,\cdot)$ spanner with $O_{\eps}(n)$ lightness, and a $+(4+\eps) W(\cdot,\cdot)$ spanner with $O_{\eps}(n^{2/3})$ lightness. These are the first known additive spanners with nontrivial lightness guarantees. All of the above spanners can be constructed in polynomial time. △ Less

Submitted 7 May, 2021; v1 submitted 17 March, 2021; originally announced March 2021.

Multi-level Weighted Additive Spanners

Authors: Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, Richard Spence

Abstract: Given a graph $G = (V,E)$, a subgraph $H$ is an \emph{additive $+β$ spanner} if $\dist_H(u,v) \le \dist_G(u,v) + β$ for all $u, v \in V$. A \emph{pairwise spanner} is a spanner for which the above inequality only must hold for specific pairs $P \subseteq V \times V$ given on input, and when the pairs have the structure $P = S \times S$ for some subset $S \subseteq V$, it is specifically called a \… ▽ More Given a graph $G = (V,E)$, a subgraph $H$ is an \emph{additive $+β$ spanner} if $\dist_H(u,v) \le \dist_G(u,v) + β$ for all $u, v \in V$. A \emph{pairwise spanner} is a spanner for which the above inequality only must hold for specific pairs $P \subseteq V \times V$ given on input, and when the pairs have the structure $P = S \times S$ for some subset $S \subseteq V$, it is specifically called a \emph{subsetwise spanner}. Spanners in unweighted graphs have been studied extensively in the literature, but have only recently been generalized to weighted graphs. In this paper, we consider a multi-level version of the subsetwise spanner in weighted graphs, where the vertices in $S$ possess varying level, priority, or quality of service (QoS) requirements, and the goal is to compute a nested sequence of spanners with the minimum number of total edges. We first generalize the $+2$ subsetwise spanner of [Pettie 2008, Cygan et al., 2013] to the weighted setting. We experimentally measure the performance of this and several other algorithms for weighted additive spanners, both in terms of runtime and sparsity of output spanner, when applied at each level of the multi-level problem. Spanner sparsity is compared to the sparsest possible spanner satisfying the given error budget, obtained using an integer programming formulation of the problem. We run our experiments with respect to input graphs generated by several different random graph generators: Erdős--Rényi, Watts--Strogatz, Barabási--Albert, and random geometric models. By analyzing our experimental results we developed a new technique of changing an initialization parameter value that provides better performance in practice. △ Less

Submitted 29 March, 2021; v1 submitted 10 February, 2021; originally announced February 2021.

On the Readability of Abstract Set Visualizations

Authors: Markus Wallinger, Ben Jacobsen, Stephen Kobourov, Martin Nöllenburg

Abstract: Set systems are used to model data that naturally arises in many contexts: social networks have communities, musicians have genres, and patients have symptoms. Visualizations that accurately reflect the information in the underlying set system make it possible to identify the set elements, the sets themselves, and the relationships between the sets. In static contexts, such as print media or infog… ▽ More Set systems are used to model data that naturally arises in many contexts: social networks have communities, musicians have genres, and patients have symptoms. Visualizations that accurately reflect the information in the underlying set system make it possible to identify the set elements, the sets themselves, and the relationships between the sets. In static contexts, such as print media or infographics, it is necessary to capture this information without the help of interactions. With this in mind, we consider three different systems for medium-sized set data, LineSets, EulerView, and MetroSets, and report the results of a controlled human-subjects experiment comparing their effectiveness. Specifically, we evaluate the performance, in terms of time and error, on tasks that cover the spectrum of static set-based tasks. We also collect and analyze qualitative data about the three different visualization systems. Our results include statistically significant differences, suggesting that MetroSets performs and scales better. △ Less

Submitted 3 May, 2021; v1 submitted 20 January, 2021; originally announced January 2021.

Comments: in IEEE Transactions on Visualization and Computer Graphics (2021). Supplementary material can be found on https://osf.io/nvd8e/

The Language of Food during the Pandemic: Hints about the Dietary Effects of Covid-19

Authors: Hoang Van, Ahmad Musa, Mihai Surdeanu, Stephen Kobourov

Abstract: We study the language of food on Twitter during the pandemic lockdown in the United States, focusing on the two month period of March 15 to May 15, 2020. Specifically, we analyze over770,000 tweets published during the lockdown and the equivalent period in the five previous years and highlight several worrying trends. First, we observe that during the lockdown there was a notable shift from mentio… ▽ More We study the language of food on Twitter during the pandemic lockdown in the United States, focusing on the two month period of March 15 to May 15, 2020. Specifically, we analyze over770,000 tweets published during the lockdown and the equivalent period in the five previous years and highlight several worrying trends. First, we observe that during the lockdown there was a notable shift from mentions of healthy foods to unhealthy foods. Second, we show an increased pointwise mutual information of depression hashtags with food-related tweets posted during the lockdown and an increased association between depression hashtags and unhealthy foods, tobacco, and alcohol during the lockdown. △ Less

Submitted 14 October, 2020; originally announced October 2020.

Comments: 9 page of main contents plus 1 page of references. 4 figures and 9 tables

Polygons with Prescribed Angles in 2D and 3D

Authors: Alon Efrat, Radoslav Fulek, Stephen Kobourov, Csaba D. Tóth

Abstract: We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=(α_0,\ldots, α_{n-1})$, $α_i\in (-π,π)$, for $i\in\{0,\ldots, n-1\}$. The problem of realizing $A$ by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied p… ▽ More We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=(α_0,\ldots, α_{n-1})$, $α_i\in (-π,π)$, for $i\in\{0,\ldots, n-1\}$. The problem of realizing $A$ by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an \emph{angle graph}. In 2D, we characterize sequences $A$ for which every generic polygon $P\subset \mathbb{R}^2$ realizing $A$ has at least $c$ crossings, for every $c\in \mathbb{N}$, and describe an efficient algorithm that constructs, for a given sequence $A$, a generic polygon $P\subset \mathbb{R}^2$ that realizes $A$ with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence $A$ can be realized by a (not necessarily generic) polygon $P\subset \mathbb{R}^3$, and for every realizable sequence the algorithm finds a realization. △ Less

Submitted 1 November, 2020; v1 submitted 24 August, 2020; originally announced August 2020.

Comments: 15 pages, 9 figures, a new section about self-intersecting realizations in 3D

MetroSets: Visualizing Sets as Metro Maps

Authors: Ben Jacobsen, Markus Wallinger, Stephen Kobourov, Martin Nöllenburg

Abstract: We propose MetroSets, a new, flexible online tool for visualizing set systems using the metro map metaphor. We model a given set system as a hypergraph $\mathcal{H} = (V, \mathcal{S})$, consisting of a set $V$ of vertices and a set $\mathcal{S}$, which contains subsets of $V$ called hyperedges. Our system then computes a metro map representation of $\mathcal{H}$, where each hyperedge $E$ in… ▽ More We propose MetroSets, a new, flexible online tool for visualizing set systems using the metro map metaphor. We model a given set system as a hypergraph $\mathcal{H} = (V, \mathcal{S})$, consisting of a set $V$ of vertices and a set $\mathcal{S}$, which contains subsets of $V$ called hyperedges. Our system then computes a metro map representation of $\mathcal{H}$, where each hyperedge $E$ in $\mathcal{S}$ corresponds to a metro line and each vertex corresponds to a metro station. Vertices that appear in two or more hyperedges are drawn as interchanges in the metro map, connecting the different sets. MetroSets is based on a modular 4-step pipeline which constructs and optimizes a path-based hypergraph support, which is then drawn and schematized using metro map layout algorithms. We propose and implement multiple algorithms for each step of the MetroSet pipeline and provide a functional prototype with easy-to-use preset configurations. Furthermore, using several real-world datasets, we perform an extensive quantitative evaluation of the impact of different pipeline stages on desirable properties of the generated maps, such as octolinearity, monotonicity, and edge uniformity. △ Less

Submitted 13 May, 2021; v1 submitted 21 August, 2020; originally announced August 2020.

Comments: 19 pages; accepted for IEEE INFOVIS 2020; for associated live system, see http://metrosets.ac.tuwien.ac.at

Journal ref: IEEE TVCG 27(2):1257-1267 (2021)

Drawing Shortest Paths in Geodetic Graphs

Authors: Sabine Cornelsen, Maximilian Pfister, Henry Förster, Martin Gronemann, Michael Hoffmann, Stephen Kobourov, Thomas Schneck

Abstract: Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph $G$, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of $G$, i.e., a drawing of $G$ in which the curves of any two shortest paths meet at most once? We… ▽ More Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph $G$, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of $G$, i.e., a drawing of $G$ in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing. △ Less

Submitted 17 August, 2020; originally announced August 2020.

Comments: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Graph Drawing via Gradient Descent, $(GD)^2$

Authors: Reyan Ahmed, Felice De Luca, Sabin Devkota, Stephen Kobourov, Mingwei Li

Abstract: Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Graph Drawing via Gradient Descent, $(GD)^2$, that can handle multi… ▽ More Readability criteria, such as distance or neighborhood preservation, are often used to optimize node-link representations of graphs to enable the comprehension of the underlying data. With few exceptions, graph drawing algorithms typically optimize one such criterion, usually at the expense of others. We propose a layout approach, Graph Drawing via Gradient Descent, $(GD)^2$, that can handle multiple readability criteria. $(GD)^2$ can optimize any criterion that can be described by a smooth function. If the criterion cannot be captured by a smooth function, a non-smooth function for the criterion is combined with another smooth function, or auto-differentiation tools are used for the optimization. Our approach is flexible and can be used to optimize several criteria that have already been considered earlier (e.g., obtaining ideal edge lengths, stress, neighborhood preservation) as well as other criteria which have not yet been explicitly optimized in such fashion (e.g., vertex resolution, angular resolution, aspect ratio). We provide quantitative and qualitative evidence of the effectiveness of $(GD)^2$ with experimental data and a functional prototype: \url{http://hdc.cs.arizona.edu/~mwli/graph-drawing/}. △ Less

Submitted 12 August, 2020; originally announced August 2020.

Comments: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

The Turing Test for Graph Drawing Algorithms

Authors: Helen C. Purchase, Daniel Archambault, Stephen Kobourov, Martin Nöllenburg, Sergey Pupyrev, Hsiang-Yun Wu

Abstract: Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on `small' graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by gra… ▽ More Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on `small' graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by graph drawing algorithms, although this is not always the case for graphs drawn by force-directed or multi-dimensional scaling algorithms, making these good candidates for Turing Test success. We show that, in general, hand-drawn graphs are judged to be of higher quality than automatically generated ones, although this result varies with graph size and algorithm. △ Less

Submitted 19 August, 2020; v1 submitted 11 August, 2020; originally announced August 2020.

Comments: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

On Random Graph Properties

Authors: Hang Chen, Vahan Huroyan, Stephen Kobourov, Myroslav Kryven

Abstract: We consider 15 properties of labeled random graphs that are of interest in the graph-theoretical and the graph mining literature, such as clustering coefficients, centrality measures, spectral radius, degree assortativity, treedepth, treewidth, etc. We analyze relationships and correlations between these properties. Whereas for graphs on a small number of vertices we can exactly compute the averag… ▽ More We consider 15 properties of labeled random graphs that are of interest in the graph-theoretical and the graph mining literature, such as clustering coefficients, centrality measures, spectral radius, degree assortativity, treedepth, treewidth, etc. We analyze relationships and correlations between these properties. Whereas for graphs on a small number of vertices we can exactly compute the average values and range for each property of interest, this becomes infeasible for larger graphs. We show that graphs generated by the \ErdosRenyi graph generator with $p = 1/2$ model well the underlying space of all labeled graphs with a fixed number of vertices. The later observation allows us to analyze properties and correlations between these properties for larger graphs. We then use linear and non-linear models to predict a given property based on the others and for each property, we find the most predictive subset. We experimentally show that pairs and triples of properties have high predictive power, making it possible to estimate computationally expensive to compute properties with ones for which there are efficient algorithms. △ Less

Submitted 23 June, 2022; v1 submitted 3 March, 2020; originally announced March 2020.

Weighted Additive Spanners

Authors: Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen Kobourov, Richard Spence

Abstract: A \emph{spanner} of a graph $G$ is a subgraph $H$ that approximately preserves shortest path distances in $G$. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured \emph{multiplicatively}. In this work, we investigate whether one can similarly ext… ▽ More A \emph{spanner} of a graph $G$ is a subgraph $H$ that approximately preserves shortest path distances in $G$. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured \emph{multiplicatively}. In this work, we investigate whether one can similarly extend constructions of spanners with purely \emph{additive} error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic $+2$ and $+4$ unweighted spanners (both all-pairs and pairwise) to $+2W$ and $+4W$ weighted spanners, where $W$ is the maximum edge weight. Specifically, we show that a weighted graph $G$ contains all-pairs (pairwise) $+2W$ and $+4W$ weighted spanners of size $O(n^{3/2})$ and $\widetilde{O}(n^{7/5})$ ($O(np^{1/3})$ and $O(np^{2/7})$) respectively. For a technical reason, the $+6$ unweighted spanner becomes a $+8W$ weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that $G$ contains all-pairs (pairwise) $+8W$ weighted spanners of size $O(n^{4/3})$ ($O(np^{1/4})$). △ Less

Submitted 29 June, 2021; v1 submitted 15 February, 2020; originally announced February 2020.

Kruskal-based approximation algorithm for the multi-level Steiner tree problem

Authors: Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm, Stephen Kobourov, Richard Spence

Abstract: We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals $T$ require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals $u$, $v$ with priorities $P(u)$, $P(v)$ are connected using edges of rate $\min\{P(u),P(v)\}$ or better. Th… ▽ More We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals $T$ require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals $u$, $v$ with priorities $P(u)$, $P(v)$ are connected using edges of rate $\min\{P(u),P(v)\}$ or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio $c \log \log n$, where $n$ is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a $\min\{2(\ln |T|+1), \ell ρ\}$-approximation in this setting, where $ρ$ is an approximation ratio for a heuristic solver for the Steiner tree problem and $\ell$ is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with $ρ\approx 1.39$, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal's minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib. △ Less

Submitted 15 May, 2020; v1 submitted 15 February, 2020; originally announced February 2020.

Packing Trees into 1-planar Graphs

Authors: Felice De Luca, Emilio Di Giacomo, Seok-Hee Hong, Stephen Kobourov, William Lenhart, Giuseppe Liotta, Henk Meijer, Alessandra Tappini, Stephen Wismath

Abstract: We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two path… ▽ More We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with $n \geq 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \leq 10$. △ Less

Submitted 5 November, 2019; originally announced November 2019.

Same Stats, Different Graphs: Exploring the Space of Graphs in Terms of Graph Properties

Authors: Hang Chen, Vahan Huroyan, Utkarsh Soni, Yafeng Lu, Ross Maciejewski, Stephen Kobourov

Abstract: Data analysts commonly utilize statistics to summarize large datasets. While it is often sufficient to explore only the summary statistics of a dataset (e.g., min/mean/max), Anscombe's Quartet demonstrates how such statistics can be misleading. We consider a similar problem in the context of graph mining. To study the relationships between different graph properties, we examine low-order non-isomo… ▽ More Data analysts commonly utilize statistics to summarize large datasets. While it is often sufficient to explore only the summary statistics of a dataset (e.g., min/mean/max), Anscombe's Quartet demonstrates how such statistics can be misleading. We consider a similar problem in the context of graph mining. To study the relationships between different graph properties, we examine low-order non-isomorphic graphs and provide a simple visual analytics system to explore correlations across multiple graph properties. However, for larger graphs, studying the entire space quickly becomes intractable. We use different random graph generation methods to further look into the distribution of graph properties for higher order graphs and investigate the impact of various sampling methodologies. We also describe a method for generating many graphs that are identical over a number of graph properties and statistics yet are clearly different and identifiably distinct. △ Less

Submitted 4 November, 2019; originally announced November 2019.

Comments: This article is publish in IEEE Transactions on Visualization and Computer Graphics. See Early Access(https://ieeexplore.ieee.org/abstract/document/8863985). This is a journal version of a paper arXiv:1808.09913 that appeared in the proceedings of the 26th Symposium on Graph Drawing and Network Visualization (GD'18)

Multi-Perspective, Simultaneous Embedding

Authors: Md Iqbal Hossain, Vahan Huroyan, Stephen Kobourov, Raymundo Navarrete

Abstract: We describe MPSE: a Multi-Perspective Simultaneous Embedding method for visualizing high-dimensional data, based on multiple pairwise distances between the data points. Specifically, MPSE computes positions for the points in 3D and provides different views into the data by means of 2D projections (planes) that preserve each of the given distance matrices. We consider two versions of the problem: f… ▽ More We describe MPSE: a Multi-Perspective Simultaneous Embedding method for visualizing high-dimensional data, based on multiple pairwise distances between the data points. Specifically, MPSE computes positions for the points in 3D and provides different views into the data by means of 2D projections (planes) that preserve each of the given distance matrices. We consider two versions of the problem: fixed projections and variable projections. MPSE with fixed projections takes as input a set of pairwise distance matrices defined on the data points, along with the same number of projections and embeds the points in 3D so that the pairwise distances are preserved in the given projections. MPSE with variable projections takes as input a set of pairwise distance matrices and embeds the points in 3D while also computing the appropriate projections that preserve the pairwise distances. The proposed approach can be useful in multiple scenarios: from creating simultaneous embedding of multiple graphs on the same set of vertices, to reconstructing a 3D object from multiple 2D snapshots, to analyzing data from multiple points of view. We provide a functional prototype of MPSE that is based on an adaptive and stochastic generalization of multi-dimensional scaling to multiple distances and multiple variable projections. We provide an extensive quantitative evaluation with datasets of different sizes and using different number of projections, as well as several examples that illustrate the quality of the resulting solutions. △ Less

Submitted 5 August, 2020; v1 submitted 13 September, 2019; originally announced September 2019.

Graph Spanners: A Tutorial Review

Authors: Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Richard Spence

Abstract: This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we… ▽ More This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners. △ Less

Submitted 13 March, 2020; v1 submitted 6 September, 2019; originally announced September 2019.

Comments: Many more papers added from the previous version, as well as significant expansion of results presented

The QuaSEFE Problem

Authors: Patrizio Angelini, Henry Förster, Michael Hoffmann, Michael Kaufmann, Stephen Kobourov, Giuseppe Liotta, Maurizio Patrignani

Abstract: We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. We show that a triple consisting of two planar graphs and a tree admit a QuaSEFE. This result also implies that a pair consisting of a 1-planar grap… ▽ More We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. We show that a triple consisting of two planar graphs and a tree admit a QuaSEFE. This result also implies that a pair consisting of a 1-planar graph and a planar graph admits a QuaSEFE. We show several other positive results for triples of planar graphs, in which certain structural properties for their common subgraphs are fulfilled. For the case in which simplicity is also required, we give a triple consisting of two quasiplanar graphs and a star that does not admit a QuaSEFE. Moreover, in contrast to the planar SEFE problem, we show that it is not always possible to obtain a QuaSEFE for two matchings if the quasiplanar drawing of one matching is fixed. △ Less

Submitted 23 August, 2019; originally announced August 2019.

Comments: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

MSC Class: 68R10

Computing Stable Demers Cartograms

Authors: Soeren Nickel, Max Sondag, Wouter Meulemans, Markus Chimani, Stephen Kobourov, Jaakko Peltonen, Martin Nöllenburg

Abstract: Cartograms are popular for visualizing numerical data for map regions. Maintaining correct adjacencies is a primary quality criterion for cartograms. When there are multiple data values per region (over time or different datasets) shown as animated or juxtaposed cartograms, preserving the viewer's mental-map in terms of stability between cartograms is another important criterion. We present a meth… ▽ More Cartograms are popular for visualizing numerical data for map regions. Maintaining correct adjacencies is a primary quality criterion for cartograms. When there are multiple data values per region (over time or different datasets) shown as animated or juxtaposed cartograms, preserving the viewer's mental-map in terms of stability between cartograms is another important criterion. We present a method to compute stable Demers cartograms, where each region is shown as a square and similar data yield similar cartograms. We enforce orthogonal separation constraints with linear programming, and measure quality in terms of keeping adjacent regions close (cartogram quality) and using similar positions for a region between the different data values (stability). Our method guarantees ability to connect most lost adjacencies with minimal leaders. Experiments show our method yields good quality and stability. △ Less

Submitted 21 August, 2019; v1 submitted 20 August, 2019; originally announced August 2019.

Comments: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

Stress-Plus-X (SPX) Graph Layout

Authors: Sabin Devkota, Reyan Ahmed, Felice De Luca, Katherine E. Isaacs, Stephen Kobourov

Abstract: Stress, edge crossings, and crossing angles play an important role in the quality and readability of graph drawings. Most standard graph drawing algorithms optimize one of these criteria which may lead to layouts that are deficient in other criteria. We introduce an optimization framework, Stress-Plus-X (SPX), that simultaneously optimizes stress together with several other criteria: edge crossing… ▽ More Stress, edge crossings, and crossing angles play an important role in the quality and readability of graph drawings. Most standard graph drawing algorithms optimize one of these criteria which may lead to layouts that are deficient in other criteria. We introduce an optimization framework, Stress-Plus-X (SPX), that simultaneously optimizes stress together with several other criteria: edge crossings, minimum crossing angle, and upwardness (for directed acyclic graphs). SPX achieves results that are close to the state-of-the-art algorithms that optimize these metrics individually. SPX is flexible and extensible and can optimize a subset or all of these criteria simultaneously. Our experimental analysis shows that our joint optimization approach is successful in drawing graphs with good performance across readability criteria. △ Less

Submitted 23 August, 2019; v1 submitted 4 August, 2019; originally announced August 2019.

Comments: 25 pages, 12 figures, accepted in the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

Symmetry Detection and Classification in Drawings of Graphs

Authors: Felice De Luca, Md Iqbal Hossain, Stephen Kobourov

Abstract: Symmetry is a key feature observed in nature (from flowers and leaves, to butterflies and birds) and in human-made objects (from paintings and sculptures, to manufactured objects and architectural design). Rotational, translational, and especially reflectional symmetries, are also important in drawings of graphs. Detecting and classifying symmetries can be very useful in algorithms that aim to cre… ▽ More Symmetry is a key feature observed in nature (from flowers and leaves, to butterflies and birds) and in human-made objects (from paintings and sculptures, to manufactured objects and architectural design). Rotational, translational, and especially reflectional symmetries, are also important in drawings of graphs. Detecting and classifying symmetries can be very useful in algorithms that aim to create symmetric graph drawings and in this paper we present a machine learning approach for these tasks. Specifically, we show that deep neural networks can be used to detect reflectional symmetries with 92% accuracy. We also build a multi-class classifier to distinguish between reflectional horizontal, reflectional vertical, rotational, and translational symmetries. Finally, we make available a collection of images of graph drawings with specific symmetric features that can be used in machine learning systems for training, testing and validation purposes. Our datasets, best trained ML models, source code are available online. △ Less

Submitted 26 August, 2019; v1 submitted 1 July, 2019; originally announced July 2019.

Comments: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

Multi-level tree based approach for interactive graph visualization with semantic zoom

Authors: Felice De Luca, Iqbal Hossain, Kathryn Gray, Stephen Kobourov, Katy Börner

Abstract: Human subject studies that map-like visualizations are as good or better than standard node-link representations of graphs, in terms of task performance, memorization and recall of the underlying data, and engagement [SSKB14, SSKB15]. With this in mind, we propose the Zoomable Multi-Level Tree (ZMLT) algorithm for multi-level tree-based, map-like visualization of large graphs. We propose seven des… ▽ More Human subject studies that map-like visualizations are as good or better than standard node-link representations of graphs, in terms of task performance, memorization and recall of the underlying data, and engagement [SSKB14, SSKB15]. With this in mind, we propose the Zoomable Multi-Level Tree (ZMLT) algorithm for multi-level tree-based, map-like visualization of large graphs. We propose seven desirable properties that such visualization should maintain and an algorithm that accomplishes them. (1) The abstract trees represent the underlying graph appropriately at different level of details; (2) The embedded trees represent the underlying graph appropriately at different levels of details; (3) At every level of detail we show real vertices and real paths from the underlying graph; (4) If any node or edge appears in a given level, then they also appear in all deeper levels; (5) All nodes at the current level and higher levels are labeled and there are no label overlaps; (6) There are no edge crossings on any level; (7) The drawing area is proportional to the total area of the labels. This algorithm is implemented and we have a functional prototype for the interactive interface in a web browser. △ Less

Submitted 9 December, 2019; v1 submitted 13 June, 2019; originally announced June 2019.

Multi-Level Graph Sketches via Single-Level Solvers

Authors: Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, Richard Spence

Abstract: Given an undirected weighted graph $G(V,E)$, a constrained sketch over a terminal set $T\subset V$ is a subgraph $G'$ that connects the terminal vertices while satisfying a given set of constraints. Examples include Steiner trees (preserving connectivity among $T$) and subsetwise spanners (preserving shortest path distances up to a stretch factor). Multi-level constrained terminal sketches are gen… ▽ More Given an undirected weighted graph $G(V,E)$, a constrained sketch over a terminal set $T\subset V$ is a subgraph $G'$ that connects the terminal vertices while satisfying a given set of constraints. Examples include Steiner trees (preserving connectivity among $T$) and subsetwise spanners (preserving shortest path distances up to a stretch factor). Multi-level constrained terminal sketches are generalizations in which terminal vertices require different levels or grades of service and each terminal pair is connected with edges of at least the minimum required level of the two terminals. This paper gives a flexible procedure for computing a broad class of multi-level graph sketches, which encompasses multi-level graph spanners, Steiner trees, and $k$--connected subgraphs as a few special cases. The proposed procedure is modular, i.e., it relies on availability of a single-level solver module (be it an oracle or approximation algorithm). One key result is that an $\ell$--level constrained terminal sketch can be computed with $\log\ell$ queries of the solver module while producing feasible solutions with approximation guarantees independent of $\ell$. Additionally, a new polynomial time algorithm for computing a subsetwise spanner is proposed. We show that for $k\in\N$, $\eps>0$, and $T\subset V$, there is a subsetwise $(2k-1)(1+\eps)$--spanner with total weight $O(|T|^\frac1kW(\ST(G,T)))$, where $W(\ST(G,T))$ is the weight of the Steiner tree of $G$ over the subset $T$. This is the first algorithm and weight guarantee for a multiplicative subsetwise spanner for nonplanar graphs. Numerical experiments are also done to illustrate the performance of the proposed algorithms. △ Less

Submitted 15 October, 2019; v1 submitted 1 May, 2019; originally announced May 2019.

Approximation algorithms and an integer program for multi-level graph spanners

Authors: Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, Richard Spence

Abstract: Given a weighted graph $G(V,E)$ and $t \ge 1$, a subgraph $H$ is a \emph{$t$--spanner} of $G$ if the lengths of shortest paths in $G$ are preserved in $H$ up to a multiplicative factor of $t$. The \emph{subsetwise spanner} problem aims to preserve distances in $G$ for only a subset of the vertices. We generalize the minimum-cost subsetwise spanner problem to one where vertices appear on multiple l… ▽ More Given a weighted graph $G(V,E)$ and $t \ge 1$, a subgraph $H$ is a \emph{$t$--spanner} of $G$ if the lengths of shortest paths in $G$ are preserved in $H$ up to a multiplicative factor of $t$. The \emph{subsetwise spanner} problem aims to preserve distances in $G$ for only a subset of the vertices. We generalize the minimum-cost subsetwise spanner problem to one where vertices appear on multiple levels, which we call the \emph{multi-level graph spanner} (MLGS) problem, and describe two simple heuristics. Applications of this problem include road/network building and multi-level graph visualization, especially where vertices may require different grades of service. We formulate a 0--1 integer linear program (ILP) of size $O(|E||V|^2)$ for the more general minimum \emph{pairwise spanner problem}, which resolves an open question by Sigurd and Zachariasen on whether this problem admits a useful polynomial-size ILP. We extend this ILP formulation to the MLGS problem, and evaluate the heuristic and ILP performance on random graphs of up to 100 vertices and 500 edges. △ Less

Submitted 1 April, 2019; originally announced April 2019.

Comments: This paper has been accepted in the Special Event on Analysis of Experimental Algorithms (SEA^2 2019)

Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains

Authors: Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael Goodrich, Stephen Kobourov, Pedro Matias, Valentin Polishchuk

Abstract: We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which a… ▽ More We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which are a central part in straight skeleton algorithms) in $O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce a narcissistic variant of the $k$-attribute stable matching model, and solve it in $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time $2$-approximation for a 1D geometric set cover problem with applications to radio station placement. △ Less

Submitted 2 December, 2019; v1 submitted 18 February, 2019; originally announced February 2019.

Comments: 35 pages, 10 figures; v2: minor improvements, added Figure 1, and author order as in paper. v3: added funding acknowledgement

MSC Class: I.3.5 ACM Class: I.3.5

Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem

Authors: Faryad Darabi Sahneh, Alon Efrat, Stephen Kobourov, Spencer Krieger, Richard Spence

Abstract: Given a graph $G = (V,E)$ and a subset $T \subseteq V$ of terminals, a \emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the \emph{ver… ▽ More Given a graph $G = (V,E)$ and a subset $T \subseteq V$ of terminals, a \emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of $G$. We study a natural generalization of the VST problem motivated by multi-level graph construction, the \emph{vertex-weighted grade-of-service Steiner tree problem} (V-GSST), which can be stated as follows: given a graph $G$ and terminals $T$, where each terminal $v \in T$ requires a facility of a minimum grade of service $R(v)\in \{1,2,\ldots\ell\}$, compute a Steiner tree $G'$ by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in $G'$ with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on $\ell$, the number of grades of service. We then generalize the greedy algorithm of [Klein \& Ravi, 1995] to show that the V-GSST problem admits a $(2 \ln |T|)$-approximation, where $T$ is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service. △ Less

Submitted 3 May, 2019; v1 submitted 28 November, 2018; originally announced November 2018.

Recognition and Drawing of Stick Graphs

Authors: Felice De Luca, Md Iqbal Hossain, Stephen Kobourov, Anna Lubiw, Debajyoti Mondal

Abstract: A \emph{Stick graph} is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a `ground line,' a line with slope $-1$. It is an open question to decide in polynomial time whether a given bipartite graph $G$ with bipartition $A\cup B$ has a Stick representation where the vertices in $A$ and… ▽ More A \emph{Stick graph} is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a `ground line,' a line with slope $-1$. It is an open question to decide in polynomial time whether a given bipartite graph $G$ with bipartition $A\cup B$ has a Stick representation where the vertices in $A$ and $B$ correspond to horizontal and vertical segments, respectively. We prove that $G$ has a Stick representation if and only if there are orderings of $A$ and $B$ such that $G$'s bipartite adjacency matrix with rows $A$ and columns $B$ excludes three small `forbidden' submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of $A$ and $B$ permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of $A$ is given, we present an $O(|A|^3|B|^3)$-time algorithm. When neither ordering is given, we present some partial results about graphs that are, or are not, Stick representable. △ Less

Submitted 29 August, 2018; originally announced August 2018.

Comments: Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)