We study a question that lies at the intersection of classical research subjects in Topological Graph Theory and Graph Drawing: Computing a drawing of a graph with a prescribed number of crossings on a given set S of points, while ensuring that its curve complexity (i.e., maximum number of bends per edge) is bounded by a constant. We focus on trees: Let T be a tree, ϑ(T) be its thrackle number, and χ be any integer in the interval [0,ϑ(T)]. In the tangling phase we compute a topological linear embedding of T with ϑ(T) edge crossings and a constant number of spine traversals. In the untangling phase we remove edge crossings without increasing the spine traversals until we reach χ crossings. The computed linear embedding is used to construct a drawing of T on S with χ crossings and constant curve complexity. Our approach gives rise to an O(n²)-time algorithm for general trees and an O(n log n)-time algorithm for paths. We also adapt the approach to compute RAC drawings, i.e. drawings where the angles formed at edge crossings are π/2.

A well-known result by Kant [Algorithmica, 1996] implies that n-vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces are convex polygons in O(n²) area. In this paper, we present an algorithm to compute such drawings in O(n¹·⁵) area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves Θ(nk²) area, where k is the maximum size of an internal facial cycle.

We address the problem of computing a dynamic visualization of a geometric graph G as a sequence of frames. Each frame shows only a portion of the graph but their union covers G entirely. The two main requirements of our dynamic visualization are: (i) guaranteeing drawing stability, so to preserve the user’s mental map; (ii) keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of G. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.

Metaphorical maps or contact representations are visual representations of vertex-weighted graphs that rely on the geographic map metaphor. The vertices are represented by countries, the weights by the areas of the countries, and the edges by contacts/boundaries among them. The accuracy with which the weights are mapped to areas and the simplicity of the polygons representing the countries are the two classical optimization goals for metaphorical maps. Mchedlidze & Schnorr [Mchedlidze and Schnorr, 2022] presented a force-based algorithm that creates metaphorical maps that balance between these two optimization goals. Their maps look visually simple, but the accuracy of the maps is far from optimal - the countries' areas can vary up to 30% compared to required. In this paper, we provide a multi-fold extension of the algorithm in [Mchedlidze and Schnorr, 2022]. More specifically: 1) Towards improving accuracy: We introduce the notion of region stiffness and suggest a technique for varying the stiffness based on the current pressure of map regions. 2) Towards maintaining simplicity: We introduce a weight coefficient to the pressure force exerted on each polygon point based on whether the corresponding point appears along a narrow passage. 3) Towards generality: We cover, in contrast to [Mchedlidze and Schnorr, 2022], non-triangulated graphs. This is done by either generating points where more than three regions meet or by introducing holes in the metaphorical map. We perform an extended experimental evaluation that, among other results, reveals that our algorithm is able to construct metaphorical maps with nearly perfect area accuracy with a little sacrifice in their simplicity.

We study the problem of representing a graph as a storyplan, a recently introduced model for dynamic graph visualization. It is based on a sequence of frames, each showing a subset of vertices and a planar drawing of their induced subgraphs, where vertices appear and disappear over time. Namely, in the StoryPlan problem, we are given a graph and we want to decide whether there exists a total vertex appearance order for which a storyplan exists. We prove that the problem is NP-complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of the input graph. We prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP-complete if the vertex appearance order is given and we have to choose how to draw the frames.

In this work, we continue the study of the area required for convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge in the drawing is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces, and computes a convex straight-line drawing with edge-vertex resolution at least 12 on an integer grid of size (n−2+a)×(n−2+a), where a=min⁡{n−3,f}. Our result improves the previously best-known area bound of (3n−7)×(3n−7)/2 by Chrobak, Goodrich and Tamassia.

Occupational fraud affects many companies causing them economic loss and liability issues towards their clients and other entities. Detecting internal fraud requires significant effort since a huge amount of data produced by diverse systems (which are mostly in textual form) has to be processed with little automated support. In this paper, we exploit the advantages of information visualization and present a system that aims to detect occupational fraud in systems which involve a pair of entities (e.g., an employee and a client). The main visualization is a spiral on which the events are drawn according to their time-stamp. Suspicious events are considered those which appear along the same radius or on close radii. The system ranks both entities according to the specifications of the auditor and a video file of their activity is generated such that events with strong evidence of fraud appear first. The system is equipped with several visualizations that facilitate the detection procedure.

A major factor affecting the readability of a graph drawing is its resolution.In the graph drawing literature, the resolution of a drawing is either measured based on the angles formed by consecutive edges incident to a common node (angular resolution) or by the angles formed at edge crossings (crossing resolution).In this paper, we evaluate both by introducing the notion of "total resolution", that is, the minimum of the angular and crossing resolution.To the best of our knowledge, this is the first time where the problem of maximizing the total resolution of a drawing is studied.The main contribution of the paper consists of drawings of asymptotically optimal total resolution for complete graphs (circular drawings) and for complete bipartite graphs (2-layered drawings).In addition, we present and experimentally evaluate a force-directed based algorithm that constructs drawings of large total resolution.

In this paper we present an approach for incorporating a state of the art speech recognition engine into a novel assistive reading system for Greek dyslexic students. This system is being developed in the framework of the AGENT-DYSL IST project, and facilitates dyslexic children in learning to read fluently. Unlike previously presented approaches, the aim of this system is to monitor the progress and perspectives of a dyslexic user and supply personalised help. The goal of this help is to gradually increase the reading capabilities of the user, gradually diminish the assistance provided, till he is able to read as a non-dyslexic reader. Copyright © 2011 ISCA.

Boundary labeling is a relatively new labeling method. It can be useful in automating the production of technical drawings and medical maps, where it is common to explain certain parts of the drawing with text labels, arranged on its boundary so that other parts of the drawing are not obscured. In boundary labeling, we are given a rectangle R which encloses a set of n sites. Each site si is associated with an axis-parallel rectangular label li. The labels must be placed in distinct positions on the boundary of R and to be connected to their corresponding sites with polygonal lines, called leaders, so that the labels are pairwise disjoint and the leaders do not intersect each other. In this paper, we study a version of the boundary labeling problem where the sites can “float ” within a polygonal region. We present a polynomial time algorithm that produces a labeling of minimum total leader length for labels of uniform size placed in fixed positions on the boundary of R.

Dyslexia is a major barrier to success in education and later on the job as reading skills are fundamental for personal competence development. Children with dyslexia have special learning needs (e.g., more teacher support), which currently only specialized institutions can provide. However, this takes children out of their peer group and causes social problems. On the other side, there is general-purpose reading support software, which are not geared towards children with dyslexia as they lack personalization. AGENT-DYSL brings together speech and image recognition as well as semantic technologies to build a truly adaptive reading support system for children with dyslexia.

In this paper, we examine algorithmic issues related to the delayed multicast technique for video-on-demand delivery. We introduce the minimum total memory (MTM), minimum total traffic (MTT) and the minimum maximum memory per node (MMMN) delayed-multicast allocation problems. We examine these problems on two networks of practical interest, namely, the chandelier and the broom networks. We provide polynomial time algorithms for solving the MTM and the MTT problems on the chandelier network and the MTM problem on the broom network. We also show that a version of the decision-MMMN problem on a general graph is NP-complete. Finally, we present a heuristic method for obtaining a solution for the MTM problem on tree networks.

"Delayed-multicast" is a novel transmission technique which uses internal nodes in the transmission paths from the server to the clients to buffer data streams. The buffers are used to service later requests without having to start new streams from the server, thus bringing the benefits of traditional multicast without the constraint that all requests must be serviced at the same time. We describe our new scalable "delayed-multicast" framework and present an optimal resource allocation algorithm that minimizes the total bandwidth required to service a set of requests.

In this paper, we consider hot-potato packet routing of one-to-one routing patterns on $n$-node trees. By applying a ‘charging argument’, we show that any greedy hot-potato algorithm routes a one-to-one routing pattern within $2(n-1)$ steps. On the other hand, a trivial lower bound suggests that at least $3n/2$ steps are required by any oblivious greedy algorithm. As the main contribution of the paper, we tighten the $2(n-1)$ upper bound by constructing (for all sufficiently large $n$) an elaborate one-to-one packet routing problem on an $n$-node tree for which an oblivious greedy hot-potato algorithm requires at least $2n-o(n)$ steps. This improved lower bound is also shown to be valid for the minimum-distance heuristic. For trees of maximum degree $d$, we establish a lower bound of $2((d-3)/(d-2))n-o(n)$ routing steps.

In this paper, we consider the deflection worm routing problem on n/spl times/n meshes. In deflection routing, a message cannot be queued and it is always moving until it reaches its destination. In worm routing, the message is considered to be a worm, a sequence of k flits which, during the routing, follow the head of the worm, which knows the destination address. We show how to derive a deflection worm routing algorithm from a packet routing algorithm which uses queues of size O(f(N))(N is the side-length of the mesh in which the packet routing algorithm is applied). Our result generalizes the method of Newman and Schuster in which only packet routing algorithms with a maximum queue of four packets can be used.

In this paper we present the multistage off-line method, a new and rather natural way to model off-line packet routing problems, which reduces the problem of off-line packet routing to that of finding edge disjoint paths on a multistage graph. The multistage off-line method can model any kind of routing pattern on any graph and can incorporate the size of the maximum queue allowed in any processor. The paths for the packets are computed by a greedy heuristic method. Based on the multistage off-line method, we study the permutation packet routing problem on two-dimensional meshes. We ran millions of experiments based on random generated data and, for all of our experiments, we were able to compute a solution of length equal to the maximum distance a packet had to travel, and thus, match the actual lower bound for each routing pattern.

This paper shows how to stably merge two sequences A and B of sizes m and n, m ≤ n, respectively, with O(m+n) assignments, O(mlog(n/m+1)) comparisons and using only a constant amount of additional space. This result matches all known lower bounds and closes an open problem posed by Dudzinski and Dydek in 1981. Our algorithm is based on the unstable algorithm of Mannila and Ukkonen. All techniques we use have appeared in the literature in more complicated forms but were never combined together. They are powerful enough to make stable all the existing linear in-place unstable algorithms we are aware of. We also present a stable algorithm that requires a linear number of comparisons and assignments which we consider to be the simplest algorithm for in-place merging.

We study multipacket routing problems on rings of processors. We prove a new lower bound of 2n/3 routing steps for the case that k, the number of packets per processor, is at most 2. We also give an algorithm that tightens this lower bound. For the case where k > 2, the lower bound is kn/4. The trivial algorithm needs in the worst case k⌊n/2⌋ steps to terminate. An algorithm that completes the routing in kn/4 + 2.5n routing steps is given.

This paper presents the problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that $\Omega (\frac{1}{{d^2 }}) \leqslant R \leqslant \frac{{2\pi }}{d}$ for any graph. Moreover, it is proved that $R = \Theta (\frac{1}{d})$ for many graphs including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if $R = \frac{{2\pi }}{d}$ for a graph is NP-hard for $d = 4$, and by using a counting argument that $R = O(\frac{{\log d}}{{d^2 }})$ for many graphs.

Even though exact algorithms exist for permutation routine of n/sup 2/ messages on a n*n mesh of processors which require constant size queues, the constants are very large and the algorithms very complicated to implement. A novel, simple heuristic for the above problem is presented. It uses constant and very small size queues (size=2). For all the simulations run on randomly generated data, the number of routing steps that is required by the algorithm is almost equal to the maximum distance a packet has to travel. A pathological case is demonstrated where the routing takes more than the optimal, and it is proved that the upper bound on the number of required steps is O(n/sup 2/). Furthermore, it is shown that the heuristic routes in optimal time inversion, transposition, and rotations, three special routing problems that appear very often in the design of parallel algorithms.>

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/)>