•There are knight's tours in n×n boards with less than 9.25n turns and 12n crossings.•Any knight's tour in an n×n board has over 5.99n turns and 4n crossings.•Using a 2×2 formation of parallel knight ...moves helps reduce both turns and crossings.•A new knight's tour algorithm minimizes turns and crossings simultaneously.•Our new knight's tour algorithm can be generalized to 3D boards and similar pieces.
We introduce two new metrics of “simplicity” for knight's tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.25n+O(1) turns and 12n+O(1) crossings on an n×n board, and we show lower bounds of (6−ϵ)n and 4n−O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 9.25/6+o(1) and 3+o(1). Our algorithm takes linear time and is fully parallelizable, i.e., the tour can be computed in O(n2/p) time using p processors in the CREW PRAM model. We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1,4)-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.
Straight-line drawings of 1-planar graphs Brandenburg, Franz J.
Computational geometry : theory and applications,
January 2024, 2024-01-00, Volume:
116
Journal Article
Peer reviewed
Open access
A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. However, there are 1-planar graphs that do not admit a straight-line 1-planar drawing. We show that ...every 1-planar graph has a straight-line drawing with a two-coloring of the edges such that edges of the same color do not cross. Thus 1-planar graphs have geometric thickness two. In addition, the drawing is nearly 1-planar, that is, it is 1-planar if all fan-crossed edges are removed. An edge is fan-crossed if it is crossed by edges with a common vertex if it is crossed more than twice. The drawing algorithm uses high precision arithmetic with numbers with O(nlogn) digits and computes the straight-line drawing from a 1-planar drawing in linear time on a real RAM.
Recognizing and drawing IC-planar graphs Brandenburg, Franz J.; Didimo, Walter; Evans, William S. ...
Theoretical computer science,
07/2016, Volume:
636
Journal Article
Peer reviewed
Open access
We give new results about the relationship between 1-planar graphs and RACgraphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in ...such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs, the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i.e., no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar.
This paper presents a new approach to flow mapping that extracts inherent patterns from massive geographic mobility data and constructs effective visual representations of the data for the ...understanding of complex flow trends. This approach involves a new method for origin-destination flow density estimation and a new method for flow map generalization, which together can remove spurious data variance, normalize flows with control population, and detect high-level patterns that are not discernable with existing approaches. The approach achieves three main objectives in addressing the challenges for analyzing and mapping massive flow data. First, it removes the effect of size differences among spatial units via kernel-based density estimation, which produces a measurement of flow volume between each pair of origin and destination. Second, it extracts major flow patterns in massive flow data through a new flow sampling method, which filters out duplicate information in the smoothed flows. Third, it enables effective flow mapping and allows intuitive perception of flow patterns among origins and destinations without bundling or altering flow paths. The approach can work with both point-based flow data (such as taxi trips with GPS locations) and area-based flow data (such as county-to-county migration). Moreover, the approach can be used to detect and compare flow patterns at different scales or in relatively sparse flow datasets, such as migration for each age group. We evaluate and demonstrate the new approach with case studies of U.S. migration data and experiments with synthetic data.
On the complexity of the storyplan problem Binucci, Carla; Di Giacomo, Emilio; Lenhart, William J. ...
Journal of computer and system sciences,
February 2024, 2024-02-00, Volume:
139
Journal Article
Peer reviewed
Open access
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.
Planarity of streamed graphs Da Lozzo, Giordano; Rutter, Ignaz
Theoretical computer science,
12/2019, Volume:
799
Journal Article
Peer reviewed
Open access
In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream of edges e1,e2,…,em on a vertex set V. A streamed graph is ω-stream ...planar with respect to a positive integer window size ω if there exists a sequence of planar topological drawings Γi of the graphs Gi=(V,{ej|i≤j<i+ω}) such that the common graph G∩i=Gi∩Gi+1 is drawn the same in Γi and in Γi+1, for 1≤i≤m−ω. The Stream Planarity Problem with window size ω asks whether a given streamed graph is ω-stream planar. We also consider a generalization, where there is an additional backbone graph whose edges have to be present during each time step. These problems are related to several well-studied planarity problems.
We show that the Stream Planarity Problem is NP-complete even when the window size is a constant and that the variant with a backbone graph is NP-complete for all ω≥2. On the positive side, we provide O(n+ωm)-time algorithms for (i) the case ω=1 and (ii) all values of ω provided the backbone graph is 2-connected. Our results improve on the Hanani-Tutte-style algorithm proposed by Schaefer GD'14 for ω=1, which runs in O((nm)3) time.
The min–max edge crossing problem (MMECP) is a challenging and important problem arising in integrated-circuit design, information visualization, and software engineering. Drawing edges as straight ...lines in accordance with the hierarchical graph drawing standard, the goal is to reduce the maximum number of edge crossings in graphs. In this study, we propose a fast path relinking (FPR) method based on dynamic-programming local search to tackle the MMECP, where an efficient neighborhood reduction mechanism is employed to evaluate only the so-called critical vertices instead of all the vertices. Moreover, the proposed FPR can simultaneously manage a number of neighborhood moves at each search iteration, which is significantly different from all the previous approaches based on one neighborhood in the literature. Extensive computational experiments on MMECP instances show that our proposed FPR approach is relatively competitive compared to the best-performing heuristics and the optimization Gurobi solver. In particular, our algorithm improved the best-known solutions for 104 of the 301 publicly available benchmark instances. Additional experiments were conducted to elucidate the key elements and search parameters of the proposed FPR. Furthermore, we made the source code of the algorithm publicly available to facilitate its use in real applications and future research.
•A path relinking method manages only two individuals to achieve a better balance.•A neighborhood reduction strategy only evaluates the critical vertices.•A dynamic programming mechanism simultaneously manages several neighborhood moves.•The conducted experiments show the efficiency of the proposed algorithm.
Convexity-increasing morphs of planar graphs Kleist, Linda; Klemz, Boris; Lubiw, Anna ...
Computational geometry : theory and applications,
November 2019, 2019-11-00, Volume:
84
Journal Article
Peer reviewed
Open access
We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one with strictly convex ...faces while maintaining planarity at all times. Our morph is convexity-increasing, meaning that once an angle is convex, it remains convex. We give an efficient algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines. Moreover, we show that a linear number of steps is worst-case optimal.
To obtain our result, we use a well-known technique by Hong and Nagamochi for finding redrawings with convex faces while preserving y-coordinates. Using a variant of Tutte's graph drawing algorithm, we obtain a new proof of Hong and Nagamochi's result which comes with a better running time. This is of independent interest, as Hong and Nagamochi's technique serves as a building block in existing morphing algorithms.
A simple topological graph is k-quasiplanar (k≥2) if it contains no k pairwise crossing edges, and k-planar if no edge is crossed more than k times. In this paper, we explore the relationship between ...k-planarity and k-quasiplanarity to show that, for k≥2, every k-planar simple topological graph can be transformed into a (k+1)-quasiplanar simple topological graph.
On fan-crossing graphs Brandenburg, Franz J.
Theoretical computer science,
11/2020, Volume:
841
Journal Article
Peer reviewed
A fan is a set of edges with a single common endpoint. A drawing of a graph in the plane is fan-crossing if each edge can only be crossed by edges of a fan. It is fan-planar if, in addition, the ...common endpoint is on the same side of the crossed edge. A drawing is adjacency-crossing if any two edges are adjacent if they cross the same edge. Then multiple independent crossings are excluded, in which an edge is crossed by at least two edges with no common endpoint. In adjacency-crossing drawings it is allowed that an edge crosses the edges of a triangle, which is excluded for fan-crossing drawings. A graph is fan-crossing (fan-planar, adjacency-crossing) if it admits a respective drawing.
We show that every adjacency-crossing graph is fan-crossing and that there are fan-crossing graphs that are not fan-planar. Moreover, for every fan-crossing graph there is a fan-planar graph on the same set of vertices and with the same number of edges. Hence, fan-crossing and fan-planar graphs are different, but they do not differ in the density with at most 5n−10 edges for graphs of order n.
PDF
