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.
Abstract
A graph is outer k-planar if it admits a straight-line drawing in which all vertices lie on a circle and every edge is crossed by at most k other edges. We study the parameterized complexity of a broad collection of graph problems on outer k-planar graphs, with k as the parameter. Many graph problems are known to be XALP-hard when parameterized by treewidth or outerplanarity, and XNLP-hard when parameterized by pathwidth. We show that only a few such problems, including Binary CSP and Scattered Set, remain intractable on outer k-planar graphs, whereas a large class of the others become fixed-parameter tractable in this setting, assuming that an outer k-planar drawing of the input graph is given. These include List Coloring, Capacitated Dominating Set, Capacitated Vertex Cover, Target Outdegree Orientation, and Target Set Selection, among others. In addition to the algorithmic and complexity results, we establish several structural results. We show 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. We also show 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
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
Given a graph $G=(V,E)$, a (proper) $k$-coloring for $G$ is a vertex coloring with $k$ colors such that every two adjacent vertices receive different colors. Suppose that the vertex set $V$ is partitioned into some groups, a proper coloring is called fair if for every color class, the difference between the number of vertices in any two groups does not exceed a given threshold. In this paper, we investigate the parameterized complexity of the fair coloring problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the number of groups for forests and also graphs of modular-width two, even when the number of colors is equal to two. On the positive side, we prove that when the number of colors is equal to two, then the problem is FPT with respect to neighborhood diversity of the input graph. Moreover, in general, the problem is FPT with respect to neighborhood diversity and the number of groups. As a by-product, we prove that unary vector bin packing problem is W[1]-hard with respect to the dimension.
R. Javadi, Hossein Shokouhi· arXiv.org· 0 citations
Deciding whether a given graph admits a planar straight-line drawing where each vertex is placed on some point from a given finite point set is known as Point Set Embeddability and is a classical problem in graph drawing. In this paper, we study the more general embeddability question where the placement of each vertex $v$ is restricted to a list $L(v)$ of admissible points. We first study the case where the given point set is in convex position. We show that this case is NP-hard even if the given graph is a matching and bi-labeled, i.e., each vertex has at most 2 admissible points. On the positive side, we present two efficient algorithms for the case where the given graph $G$ is connected (and not necessarily bi-labeled): if $G$ is equipped with a combinatorial embedding that needs to be respected, we can solve the problem in polynomial time; otherwise we can solve it in FPT-time with regard to the maximum vertex degree. In particular, this answers an open question by Frati, Glisse, Lenhart, Liotta, Mchedlidze, and Nishat [GD'13]. We then turn our attention to the more general case where the given point set is not necessarily in convex position. Here, we show NP-hardness for bi-labeled paths; notably these graphs have a unique combinatorial embedding and maximum degree two. We also present an FPT-algorithm with respect to the vertex cover number for the special case of bi-labeled graphs. We complement this latter result by establishing paraNP-hardness in the tri-labeled setting for vertex cover number 2 and polynomial-time solvability for vertex cover number 1 and arbitrary $L$. Finally, we study optimization and extension variants, where we want to maximize the number of edges or extend a partial drawing, respectively. For the former, we show APX-hardness and for the latter, we provide a parameterized complexity dichotomy under natural extension parameters.
Thomas Depian, Joseph Dorfer, Boris Klemz et al.· arXiv.org· 0 citations
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 work studies the unambiguous complexity of the Long Path problem on DAGs under parameterization and obtains an algorithm that achieves unambiguous and co-unambiguous O ( k log n ) space while running in time polynomial in both n and k.
Ronak Bhadra, Saurya Singh, Raghunath Tewari· International Symposium on M...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
