-
Exploiting New Properties of String Net Frequency for Efficient Computation
Authors:
Peaker Guo,
Patrick Eades,
Anthony Wirth,
Justin Zobel
Abstract:
Knowing which strings in a massive text are significant -- that is, which strings are common and distinct from other strings -- is valuable for several applications, including text compression and tokenization. Frequency in itself is not helpful for significance, because the commonest strings are the shortest strings. A compelling alternative is net frequency, which has the property that strings w…
▽ More
Knowing which strings in a massive text are significant -- that is, which strings are common and distinct from other strings -- is valuable for several applications, including text compression and tokenization. Frequency in itself is not helpful for significance, because the commonest strings are the shortest strings. A compelling alternative is net frequency, which has the property that strings with positive net frequency are of maximal length. However, net frequency remains relatively unexplored, and there is no prior art showing how to compute it efficiently. We first introduce a characteristic of net frequency that simplifies the original definition. With this, we study strings with positive net frequency in Fibonacci words. We then use our characteristic and solve two key problems related to net frequency. First, \textsc{single-nf}, how to compute the net frequency of a given string of length $m$, in an input text of length $n$ over an alphabet size $σ$. Second, \textsc{all-nf}, given length-$n$ input text, how to report every string of positive net frequency. Our methods leverage suffix arrays, components of the Burrows-Wheeler transform, and solution to the coloured range listing problem. We show that, for both problems, our data structure has $O(n)$ construction cost: with this structure, we solve \textsc{single-nf} in $O(m + σ)$ time and \textsc{all-nf} in $O(n)$ time. Experimentally, we find our method to be around 100 times faster than reasonable baselines for \textsc{single-nf}. For \textsc{all-nf}, our results show that, even with prior knowledge of the set of strings with positive net frequency, simply confirming that their net frequency is positive takes longer than with our purpose-designed method.
△ Less
Submitted 23 April, 2024; v1 submitted 19 April, 2024;
originally announced April 2024.
-
CelticGraph: Drawing Graphs as Celtic Knots and Links
Authors:
Peter Eades,
Niklas Gröne,
Karsten Klein,
Patrick Eades,
Leo Schreiber,
Ulf Hailer,
Falk Schreiber
Abstract:
Celtic knots are an ancient art form often attributed to Celtic cultures, used to decorate monuments and manuscripts, and to symbolise eternity and interconnectedness. This paper describes the framework CelticGraph to draw graphs as Celtic knots and links. The drawing process raises interesting combinatorial concepts in the theory of circuits in planar graphs. Further, CelticGraph uses a novel alg…
▽ More
Celtic knots are an ancient art form often attributed to Celtic cultures, used to decorate monuments and manuscripts, and to symbolise eternity and interconnectedness. This paper describes the framework CelticGraph to draw graphs as Celtic knots and links. The drawing process raises interesting combinatorial concepts in the theory of circuits in planar graphs. Further, CelticGraph uses a novel algorithm to represent edges as Bézier curves, aiming to show each link as a smooth curve with limited curvature.
△ Less
Submitted 14 September, 2023; v1 submitted 6 September, 2023;
originally announced September 2023.
-
Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs
Authors:
Xiuge Chen,
Rajesh Chitnis,
Patrick Eades,
Anthony Wirth
Abstract:
In this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters -- maximum independent set, minimum dominating set and maximum matching -- on sparse graph classes, i.e., graphs which satisfy $m=O(n)$ where $m,n$ is the number of edges, vertices respectively. Each of the three graph parameters we consider can have size $Ω(n)$ even on sparse graph classes,…
▽ More
In this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters -- maximum independent set, minimum dominating set and maximum matching -- on sparse graph classes, i.e., graphs which satisfy $m=O(n)$ where $m,n$ is the number of edges, vertices respectively. Each of the three graph parameters we consider can have size $Ω(n)$ even on sparse graph classes, and hence for sublinear-space algorithms we are restricted to parameter estimation instead of attempting to find a solution.
△ Less
Submitted 26 May, 2023;
originally announced May 2023.
-
Shape-Faithful Graph Drawings
Authors:
Amyra Meidiana,
Seok-Hee Hong,
Peter Eades
Abstract:
Shape-based metrics measure how faithfully a drawing D represents the structure of a graph G, using the proximity graph S of D. While some limited graph classes admit proximity drawings (i.e., optimally shape-faithful drawings, where S = G), algorithms for shape-faithful drawings of general graphs have not been investigated. In this paper, we present the first study for shape-faithful drawings of…
▽ More
Shape-based metrics measure how faithfully a drawing D represents the structure of a graph G, using the proximity graph S of D. While some limited graph classes admit proximity drawings (i.e., optimally shape-faithful drawings, where S = G), algorithms for shape-faithful drawings of general graphs have not been investigated. In this paper, we present the first study for shape-faithful drawings of general graphs. First, we conduct extensive comparison experiments for popular graph layouts using the shape-based metrics, and examine the properties of highly shape-faithful drawings. Then, we present ShFR and ShSM, algorithms for shape-faithful drawings based on force-directed and stress-based algorithms, by introducing new proximity forces/stress. Experiments show that ShFR and ShSM obtain significant improvement over FR (Fruchterman-Reingold) and SM (Stress Majorization), on average 12% and 35% respectively, on shape-based metrics.
△ Less
Submitted 30 August, 2022;
originally announced August 2022.
-
New Quality Metrics for Dynamic Graph Drawing
Authors:
Amyra Meidiana,
Seok-Hee Hong,
Peter Eades
Abstract:
In this paper, we present new quality metrics for dynamic graph drawings. Namely, we present a new framework for change faithfulness metrics for dynamic graph drawings, which compare the ground truth change in dynamic graphs and the geometric change in drawings. More specifically, we present two specific instances, cluster change faithfulness metrics and distance change faithfulness metrics. We fi…
▽ More
In this paper, we present new quality metrics for dynamic graph drawings. Namely, we present a new framework for change faithfulness metrics for dynamic graph drawings, which compare the ground truth change in dynamic graphs and the geometric change in drawings. More specifically, we present two specific instances, cluster change faithfulness metrics and distance change faithfulness metrics. We first validate the effectiveness of our new metrics using deformation experiments. Then we compare various graph drawing algorithms using our metrics. Our experiments confirm that the best cluster (resp. distance) faithful graph drawing algorithms are also cluster (resp. distance) change faithful.
△ Less
Submitted 24 August, 2020; v1 submitted 18 August, 2020;
originally announced August 2020.
-
A Study of Mental Maps in Immersive Network Visualization
Authors:
Joseph Kotlarek,
Oh-Hyun Kwon,
Kwan-Liu Ma,
Peter Eades,
Andreas Kerren,
Karsten Klein,
Falk Schreiber
Abstract:
The visualization of a network influences the quality of the mental map that the viewer develops to understand the network. In this study, we investigate the effects of a 3D immersive visualization environment compared to a traditional 2D desktop environment on the comprehension of a network's structure. We compare the two visualization environments using three tasks--interpreting network structur…
▽ More
The visualization of a network influences the quality of the mental map that the viewer develops to understand the network. In this study, we investigate the effects of a 3D immersive visualization environment compared to a traditional 2D desktop environment on the comprehension of a network's structure. We compare the two visualization environments using three tasks--interpreting network structure, memorizing a set of nodes, and identifying the structural changes--commonly used for evaluating the quality of a mental map in network visualization. The results show that participants were able to interpret network structure more accurately when viewing the network in an immersive environment, particularly for larger networks. However, we found that 2D visualizations performed better than immersive visualization for tasks that required spatial memory.
△ Less
Submitted 17 January, 2020;
originally announced January 2020.
-
A Quality Metric for Symmetric Graph Drawings
Authors:
Amyra Meidiana,
Seok-Hee Hong,
Peter Eades,
Daniel Keim
Abstract:
Symmetry is an important aesthetic criteria in graph drawing and network visualisation. Symmetric graph drawings aim to faithfully represent automorphisms of graphs as geometric symmetries in a drawing.
In this paper, we design and implement a framework for quality metrics that measure symmetry, that is, how faithfully a drawing of a graph displays automorphisms as geometric symmetries. The qual…
▽ More
Symmetry is an important aesthetic criteria in graph drawing and network visualisation. Symmetric graph drawings aim to faithfully represent automorphisms of graphs as geometric symmetries in a drawing.
In this paper, we design and implement a framework for quality metrics that measure symmetry, that is, how faithfully a drawing of a graph displays automorphisms as geometric symmetries. The quality metrics are based on geometry (i.e. Euclidean distance) as well as mathematical group theory (i.e. orbits of automorphisms).
More specifically, we define two varieties of symmetry quality metrics: (1) for displaying a single automorphism as a symmetry (axial or rotational) and (2) for displaying a group of automorphisms (cyclic or dihedral). We also present algorithms to compute the symmetric quality metrics in O(n log n) time for rotational symmetry and axial symmetry.
We validate our symmetry quality metrics using deformation experiments. We then use the metrics to evaluate a number of established graph drawing layouts to compare how faithfully they display automorphisms of a graph as geometric symmetries.
△ Less
Submitted 11 October, 2019;
originally announced October 2019.
-
Multi-level Graph Drawing using Infomap Clustering
Authors:
Seok-Hee Hong,
Peter Eades,
Marnijati Torkel,
Ziyang Wang,
David Chae,
Sungpack Hong,
Daniel Langerenken,
Hassan Chafi
Abstract:
Infomap clustering finds the community structures that minimize the expected description length of a random walk trajectory; algorithms for infomap clustering run fast in practice for large graphs. In this paper we leverage the effectiveness of Infomap clustering combined with the multi-level graph drawing paradigm. Experiments show that our new Infomap based multi-level algorithm produces good vi…
▽ More
Infomap clustering finds the community structures that minimize the expected description length of a random walk trajectory; algorithms for infomap clustering run fast in practice for large graphs. In this paper we leverage the effectiveness of Infomap clustering combined with the multi-level graph drawing paradigm. Experiments show that our new Infomap based multi-level algorithm produces good visualization of large and complex networks, with significant improvement in quality metrics.
△ Less
Submitted 21 August, 2019;
originally announced August 2019.
-
A Quality Metric for Visualization of Clusters in Graphs
Authors:
Amyra Meidiana,
Seok-Hee Hong,
Peter Eades,
Daniel Keim
Abstract:
Traditionally, graph quality metrics focus on readability, but recent studies show the need for metrics which are more specific to the discovery of patterns in graphs. Cluster analysis is a popular task within graph analysis, yet there is no metric yet explicitly quantifying how well a drawing of a graph represents its cluster structure. We define a clustering quality metric measuring how well a n…
▽ More
Traditionally, graph quality metrics focus on readability, but recent studies show the need for metrics which are more specific to the discovery of patterns in graphs. Cluster analysis is a popular task within graph analysis, yet there is no metric yet explicitly quantifying how well a drawing of a graph represents its cluster structure. We define a clustering quality metric measuring how well a node-link drawing of a graph represents the clusters contained in the graph. Experiments with deforming graph drawings verify that our metric effectively captures variations in the visual cluster quality of graph drawings. We then use our metric to examine how well different graph drawing algorithms visualize cluster structures in various graphs; the results con-firm that some algorithms which have been specifically designed to show cluster structures perform better than other algorithms.
△ Less
Submitted 21 August, 2019;
originally announced August 2019.
-
Polyline Drawings with Topological Constraints
Authors:
Emilio Di Giacomo,
Peter Eades,
Giuseppe Liotta,
Henk Meijer,
Fabrizio Montecchiani
Abstract:
Let $G$ be a simple topological graph and let $Γ$ be a polyline drawing of $G$. We say that $Γ$ \emph{partially preserves the topology} of $G$ if it has the same external boundary, the same rotation system, and the same set of crossings as $G$. Drawing $Γ$ fully preserves the topology of $G$ if the planarization of $G$ and the planarization of $Γ$ have the same planar embedding. We show that if th…
▽ More
Let $G$ be a simple topological graph and let $Γ$ be a polyline drawing of $G$. We say that $Γ$ \emph{partially preserves the topology} of $G$ if it has the same external boundary, the same rotation system, and the same set of crossings as $G$. Drawing $Γ$ fully preserves the topology of $G$ if the planarization of $G$ and the planarization of $Γ$ have the same planar embedding. We show that if the set of crossing-free edges of $G$ forms a connected spanning subgraph, then $G$ admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of $G$ is not a connected spanning subgraph, the curve complexity may be $Ω(\sqrt{n})$. Concerning drawings that fully preserve the topology, we show that if $G$ has skewness $k$, it admits one such drawing with curve complexity at most $2k$; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal $2$-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.
△ Less
Submitted 21 September, 2018;
originally announced September 2018.
-
The Weighted Barycenter Drawing Recognition Problem
Authors:
Peter Eades,
Patrick Healy,
Nikola S. Nikolov
Abstract:
We consider the question of whether a given graph drawing $Γ$ of a triconnected planar graph $G$ is a weighted barycenter drawing. We answer the question with an elegant arithmetic characterisation using the faces of $Γ$. This leads to positive answers when the graph is a Halin graph, and to a polynomial time recognition algorithm when the graph is cubic.
We consider the question of whether a given graph drawing $Γ$ of a triconnected planar graph $G$ is a weighted barycenter drawing. We answer the question with an elegant arithmetic characterisation using the faces of $Γ$. This leads to positive answers when the graph is a Halin graph, and to a polynomial time recognition algorithm when the graph is cubic.
△ Less
Submitted 3 September, 2018;
originally announced September 2018.
-
Turning Cliques into Paths to Achieve Planarity
Authors:
Patrizio Angelini,
Peter Eades,
Seok-Hee Hong,
Karsten Klein,
Stephen Kobourov,
Giuseppe Liotta,
Alfredo Navarra,
Alessandra Tappini
Abstract:
Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call $h$-Clique2Path Planarity: Given a graph $G$, whose vertices are partitioned into subsets of size at most $h$, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of $G$ is planar.…
▽ More
Motivated by hybrid graph representations, we introduce and study the following beyond-planarity problem, which we call $h$-Clique2Path Planarity: Given a graph $G$, whose vertices are partitioned into subsets of size at most $h$, each inducing a clique, remove edges from each clique so that the subgraph induced by each subset is a path, in such a way that the resulting subgraph of $G$ is planar. We study this problem when $G$ is a simple topological graph, and establish its complexity in relation to $k$-planarity. We prove that $h$-Clique2Path Planarity is NP-complete even when $h=4$ and $G$ is a simple $3$-plane graph, while it can be solved in linear time, for any $h$, when $G$ is $1$-plane.
△ Less
Submitted 28 August, 2018; v1 submitted 27 August, 2018;
originally announced August 2018.
-
Drawing Big Graphs using Spectral Sparsification
Authors:
Peter Eades,
Quan Nguyen,
Seok-Hee Hong
Abstract:
Spectral sparsification is a general technique developed by Spielman et al. to reduce the number of edges in a graph while retaining its structural properties. We investigate the use of spectral sparsification to produce good visual representations of big graphs. We evaluate spectral sparsification approaches on real-world and synthetic graphs. We show that spectral sparsifiers are more effective…
▽ More
Spectral sparsification is a general technique developed by Spielman et al. to reduce the number of edges in a graph while retaining its structural properties. We investigate the use of spectral sparsification to produce good visual representations of big graphs. We evaluate spectral sparsification approaches on real-world and synthetic graphs. We show that spectral sparsifiers are more effective than random edge sampling. Our results lead to guidelines for using spectral sparsification in big graph visualization.
△ Less
Submitted 30 August, 2017; v1 submitted 29 August, 2017;
originally announced August 2017.
-
Gap-planar Graphs
Authors:
Sang Won Bae,
Jean-Francois Baffier,
Jinhee Chun,
Peter Eades,
Kord Eickmeyer,
Luca Grilli,
Seok-Hee Hong,
Matias Korman,
Fabrizio Montecchiani,
Ignaz Rutter,
Csaba D. Tóth
Abstract:
We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition is motivated by applications in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most $k$ local gaps per edge. We present re…
▽ More
We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition is motivated by applications in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most $k$ local gaps per edge. We present results on the maximum density of $k$-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of $k$-gap-planar complete graphs, and the computational complexity of recognizing $k$-gap-planar graphs.
△ Less
Submitted 27 February, 2019; v1 submitted 25 August, 2017;
originally announced August 2017.
-
Towards Faithful Graph Visualizations
Authors:
Quan Hoang Nguyen,
Peter Eades
Abstract:
Readability criteria have been addressed as a measurement of the quality of graph visualizations. In this paper, we argue that readability criteria are necessary but not sufficient. We propose a new kind of criteria, namely faithfulness, to evaluate the quality of graph layouts. We introduce a general model for quantify faithfulness, and contrast it with the well established readability criteria.…
▽ More
Readability criteria have been addressed as a measurement of the quality of graph visualizations. In this paper, we argue that readability criteria are necessary but not sufficient. We propose a new kind of criteria, namely faithfulness, to evaluate the quality of graph layouts. We introduce a general model for quantify faithfulness, and contrast it with the well established readability criteria. We show examples of common visualization techniques, such as multidimensional scaling, edge bundling and several other visualization metaphors for the study of faithfulness.
△ Less
Submitted 1 November, 2018; v1 submitted 4 January, 2017;
originally announced January 2017.
-
Simultaneous Orthogonal Planarity
Authors:
Patrizio Angelini,
Steven Chaplick,
Sabine Cornelsen,
Giordano Da Lozzo,
Giuseppe Di Battista,
Peter Eades,
Philipp Kindermann,
Jan Kratochvil,
Fabian Lipp,
and Ignaz Rutter
Abstract:
We introduce and study the $\textit{OrthoSEFE}-k$ problem: Given $k$ planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing…
▽ More
We introduce and study the $\textit{OrthoSEFE}-k$ problem: Given $k$ planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the $k$ graphs?
We show that the problem is NP-complete for $k \geq 3$ even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for $k \geq 2$ even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for $k=2$ when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.
△ Less
Submitted 30 August, 2016;
originally announced August 2016.
-
Straight-line Drawability of a Planar Graph Plus an Edge
Authors:
Peter Eades,
Seok-Hee Hong,
Giuseppe Liotta,
Naoki Katoh,
Sheung-Hung Poon
Abstract:
We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that c…
▽ More
We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing.
△ Less
Submitted 30 June, 2015; v1 submitted 24 April, 2015;
originally announced April 2015.
-
Order Preserving Matching
Authors:
Jinil Kim,
Peter Eades,
Rudolf Fleischer,
Seok-Hee Hong,
Costas S. Iliopoulos,
Kunsoo Park,
Simon J. Puglisi,
Takeshi Tokuyama
Abstract:
We introduce a new string matching problem called order-preserving matching on numeric strings where a pattern matches a text if the text contains a substring whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the string…
▽ More
We introduce a new string matching problem called order-preserving matching on numeric strings where a pattern matches a text if the text contains a substring whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching has to do with representations of order relations of a numeric string. We define prefix representation and nearest neighbor representation, which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O(n log m) time algorithm and optimize it further to obtain O(n + m log m) time. For the multiple pattern case, we give an O(n log m) time algorithm.
△ Less
Submitted 17 February, 2013;
originally announced February 2013.
-
A Force-Directed Method for Large Crossing Angle Graph Drawing
Authors:
Peter Eades,
Weidong Huang,
Seok-Hee Hong
Abstract:
Recent empirical research has indicated that human graph reading performance improves when crossing angles increase. However, crossing angle has not been used as an aesthetic criterion for graph drawing algorithms so far. In this paper, we introduce a force-directed method that aims to construct graph drawings with large crossing angles. Experiments indicate that our method significantly increases…
▽ More
Recent empirical research has indicated that human graph reading performance improves when crossing angles increase. However, crossing angle has not been used as an aesthetic criterion for graph drawing algorithms so far. In this paper, we introduce a force-directed method that aims to construct graph drawings with large crossing angles. Experiments indicate that our method significantly increases crossing angles. Surprisingly, the experimental results further demonstrate that the resulting drawings produced by our method have fewer edge crossings, a shorter total edge length and more uniform edge lengths, compared to classical spring algorithms.
△ Less
Submitted 21 December, 2010;
originally announced December 2010.
