Celtic knots, an ancient art form often linked to Celtic heritage, have been used historically in the decoration of monuments and manuscripts, often symbolizing the notions of eternity and interconnectedness. This paper introduces the framework CelticGraph designed for illustrating graphs in the style of Celtic knots and links. The process of creating these drawings 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. We also show that with our production mechanisms we can compute any 4-regular plane graph and thereby any celtic knot or link. The CelticGraph framework for drawing graphs as celtic knots and links is implemented as an add-on of Vanted, a network visualization and analysis tool.

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.

The shape-based metrics evaluate a drawing D of a large and complex graph G, by computing the similarity between G and a proximity graph S computed from D. However, existing metrics using planar proximity graphs, such as the Gabriel proximity graph with at most 3n−8 edges, fail to accurately evaluate drawings of complex dense graphs with Θ(n2) edges.This paper presents new shape-based faithfulness metrics using the β-skeleton proximity graph, which represent the skeleton shape of a set of points in the plane with up to Θ(n2) edges. Specifically, we leverage the effectiveness of the β-skeleton as a shape-based metric, and provide guidelines on the parameter β for various graph classes. Extensive experiments demonstrate that our new β-skeleton shape-based metrics can more accurately measure the faithfulness of drawings of large dense graphs, with a significant improvement of over 67% on average, than the existing Gabriel graph shape-based metrics.