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.
Abstract
Planar graphs are central to graph drawing, with extensive results on planar layouts and related structures. Every planar graph admits a planar straight-line drawing, and algorithms can guarantee additional geometric or combinatorial properties. However, it is unclear which algorithms work best in practice. Even for small graphs with near-perfect manual drawings, standard algorithms might produce poor spacing, distorted faces, or small angles. We present an experimental evaluation of planar graph drawing algorithms on a large benchmark collection of small and medium-sized planar graphs (\(10\)--\(400\) vertices). 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. The results show that no evaluated algorithm is best across all aesthetic criteria, and optimizing one visual property often worsens another. Directly optimizing visual criteria improves targeted scores, and score-guided combination of several methods gives the best aggregate results, but no simple algorithm emerges as a clear universal default. Designing a simple, robust algorithm that performs well across graph families and aesthetic criteria therefore remains an open practical problem.
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.
A graph is a mathematical structure comprising a set 𝑉 of vertices and a set 𝐸 of edges, with each edge 𝑒 corresponding to a pair of vertices called the endpoints of 𝑒 . A graph is planar if its vertices can be placed in distinct locations on a plane surface and its edges can be drawn on the plane without the edges intersecting, except at their common vertex endpoints. For a planar graph, a planarity algorithm typically outputs a combinatorial data structure that validation code can use to certify the planarity of the input graph. A planar graph drawing is typically produced by a separate algorithm. On the other hand, if an input graph is not planar, then a planarity algorithm typically outputs a minimal subgraph of the input graph that obstructs planarity. Validation code can use a minimal planarity-obstructing subgraph to certify the non-planarity of an input graph. Moreover, a minimal subgraph obstructing planarity can be used to help decide how to amend an input graph to planarize it. Graphs are used to model a very wide array of real-world problems in which there are objects and relationships between the objects. In artificial intelligence, graphs are used to help with reasoning tasks, such as about the relationship pathways between persons of interest in law enforcement or between genes, tissues, diseases, and medications in bioinformatics research. In physics, graphs and planarity are used to help compute material phase transitions, particle interactions, and electromagnetic duality. Similarly, in chemistry, graphs may be used to represent atoms and their valence bonds in molecules. Planarity testing can help determine feasible molecular arrangements because the molecular graphs for
John M. Boyer, Wanda B. K. Boyer· Journal of Open Source Softw...· 0 citations
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.
Alexander Firbas, R. Ganian, Sylvain Meunier et al.· arXiv.org· 0 citations
An upward planar drawing of a directed acyclic graph is a planar drawing where every edge is pointed upward from its tail to head. Upward planar drawings are among the most natural drawing styles of directed graphs and have been researched in a variety of different settings, recently including that of drawing extension. In the drawing extension setting, one asks: given a graph $G$ and a (typically connected) subgraph $H$ of $G$ with a drawing $\Gamma(H)$, can we complete $\Gamma(H)$ to a drawing of $G$? Drawing extension problems have been studied for numerous drawing styles; the vast majority of these are NP-hard and a typical approach aimed at circumventing their intractability is to design parameterized algorithms where the parameter measures"how much"of $G$ is still missing from the pre-drawn graph $H$. Most algorithms obtained within this framework require only a small number of edges to be missing from $H$ in order to remain efficient. In this article, we present a fixed-parameter algorithm for extending upward planar drawings which overcomes this drawback by using the $\textit{vertex+edge deletion distance}$ as the parameter, thus achieving tractability even for instances with many missing edges. A key ingredient towards our result is a novel characterization of"canonical"sets of missing edges which cross a horizontal line segment in the drawing.
V. Chekan, R. Ganian, Viktoriia Korchemna· arXiv.org· 0 citations
Graph machine learning tailored to planar graphs is developed, with an emphasis on the mathematical intuition that connects the topology of a plane embedding to the spectral and combinatorial structure ex- ploited by learning algorithms.
Satyanarayana Sanakkayala· International Journal of Com...· 0 citations
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
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
