This paper investigates the parameterized complexity of this problem and obtains an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot k})$ algorithms.
Abstract
Two-layer drawings of bipartite graphs place the vertices of each part on one of two parallel lines and draw the edges as straight-line links. Traditionally, the optimization goal is to find vertex permutations on one or both layers that minimize the induced number of edge crossings. This problem is NP-hard, and crossing-minimal solutions may still contain many crossings. Recently, there has been growing interest in an orthogonal optimization goal, namely removing all crossings by vertex splitting, i.e., replacing original vertices by two or more copies and distributing the adjacencies among them. In this paper, we study a natural extension of the two-layer vertex splitting problem in which the vertex order on one layer is constrained by a given auxiliary tree $T$, motivated by applications such as the visualization of anatomical hierarchies in the Human Reference Atlas. We investigate the parameterized complexity of this problem and obtain two main contributions: (1) a fixed-parameter algorithm with respect to the number $k$ of splits, and (2) an ETH-tight single-exponential fixed-parameter algorithm with respect to the maximum degree of $T$. Moreover, we build on the latter result to obtain an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot \log k})$ algorithms. Finally, we also implement our algorithm and show that it performs well in practice.
An edge card of a graph is obtained by deleting one edge, and a class edge-reconstruction number asks for the fewest carefully selected cards that identify the graph when its class is known. We determine the sharp universal bound for maximal planar graphs. Two selected cards always suffice, and the octahedral graph shows that two can be necessary; some maximal planar graphs are already identified by one card. The argument exploits the fact that deleting a flippable edge leaves a single quadrilateral whose two diagonals give the only possible maximal-planar completions. Degree information then rules out the competing completion, with a separate argument for graphs containing a vertex of degree three. This settles a problem posed in a 2010 survey on reconstruction numbers.
Trees arise in many applications and computing nice tree layouts is a classical problem in information visualization. In many practical settings, vertices need to be represented as rectangles with a given width and height rather than as points. When an order over the children of each vertex is given, polynomial-time algorithms are known that produce drawings adhering to various drawing conventions. However, in many applications, the order of children carries no semantic meaning, and choosing it well can significantly reduce the drawing's width. In this paper, we study the problem \textsc{Min-Width Tree Drawing with Reordering} (\textsc{MWD}): given a rooted tree whose vertices have prescribed widths, find a sibling order at each internal vertex that minimizes the width of the resulting layered drawing. We show that the problem is \textsf{NP}-complete, even on binary trees with unit-width vertices. We present a mixed integer linear program that solves \textsc{MWD} exactly on moderately sized instances, and a heuristic that is fast and delivers good results in practice. We evaluate both approaches against a baseline on synthetic and real-world datasets, where reordering reduces drawing width by a median of $\approx20\%$ and by up to $\approx55\%$ on individual instances. The heuristic computes its layouts in under a second and, when the MILP proves optimality, it stays within $25\%$ of the optimal width in three-quarters of all instances.
Mark Wallinger, Oscar Navarro, Stephen G. Kobourov· arXiv.org· 0 citations
It is shown that outer k-planar graphs have mim-width at most k+2, that graphs of cut-width at most k are outer 2k-planar, and that graphs of feedback edge set number at most k are outer 6k-planar, and that many graph parameters are incomparable with outer k-planarity, thereby clarifying its position within the graph parameter hierarchy.
The study compares established algorithms from the graph drawing literature, practical force-directed and pressure-based heuristics, and new optimization-based methods that directly improve visual properties such as edge-length uniformity, face-area balance, and angular resolution to show that no evaluated algorithm is best across all aesthetic criteria.
This paper presents an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model and gives a 1.5-competitive algorithm and provide a matching lower bound.
Júlia Baligács, B. Bosek, Y. Disser et al.· Embedded Systems and Applica...· 1 citation
Orthogonal planar drawings constitute a classical and mainstream research topic in graph drawing due to their clarity and wide applicability. In an orthogonal planar drawing of a graph, each face is represented as an orthogonal polygon, that is, a polygon whose edges are either horizontal or vertical. Yet a planar graph admits such a representation if and only if its maximum degree is at most four. In this paper, we consider planar polyline drawings of graphs with unrestricted maximum degree. We focus on drawings that are ``close to orthogonal'', where closeness is measured by the number of faces that are not orthogonal polygons. We show that, even when the input graph is triconnected and thus has a unique planar embedding, the problem of testing whether there exists a planar polyline drawing with at most $h$ non-orthogonal faces is NP-complete. Motivated by this computational hardness, we study parameterized and approximation algorithms. In the fixed-embedding setting, we prove that the problem admits linear-time FPT algorithms parameterized by (i) the outerplanarity index and (ii) the natural parameter $h$. In addition, we provide an FPT algorithm parameterized by the treewidth and a polynomial-time approximation scheme. In the variable-embedding setting, we give an FPT algorithm parameterized by treewidth for biconnected graphs.
Patrizio Angelini, Sabine Cornelsen, G. Da Lozzo et al.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
