Search
Search Results
-
Splitting Plane Graphs to Outerplanarity
Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph...
-
Distance Transform in Images and Connected Plane Graphs
The distance transform (DT) serves as a crucial operation in numerous image processing and pattern recognition methods, finding broad applications in...
-
Computing Bend-Minimum Orthogonal Drawings of Plane Series–Parallel Graphs in Linear Time
A planar orthogonal drawing of a planar 4-graph G (i.e., a planar graph with vertex-degree at most four) is a crossing-free drawing that maps each...
-
Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs
A conflict-free coloring of a graph G is a (partial) coloring of its vertices such that every vertex u has a neighbor whose assigned color is unique...
-
Plane Multigraphs with One-Bend and Circular-Arc Edges of a Fixed Angle
For an angle \(\alpha \in (0,\pi )\) , we consider plane graphs and...
-
Mixed Metric Dimension of Some Plane Graphs
Let G be a finite undirected simple connected graph with vertex set V(G) and edge set E(G). A vertex...
-
Paired restraint domination in extended supergrid graphs
Consider a graph G with vertex set V ( G ) and edge set E ( G ). A subset D of V ( G ) is said to be a dominating set of G if every vertex not in D is...
-
Cops and Robbers on 1-Planar Graphs
Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and robber move along...
-
String Graphs with Precise Number of Intersections
A string graph is an intersection graph of curves in the plane. A k-string graph is a graph with a string representation in which every pair of...
-
Upward Book Embeddability of st-Graphs: Complexity and Algorithms
A k - page upward book embedding ( k UBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the...
-
Start thinking in graphs: using graphs to address critical attack paths in a Microsoft cloud tenant
The challenge of securing IT environments has reached a new complexity level as a growing number of organisations adopt cloud solutions. This trend...
-
On Embeddability of Unit Disk Graphs Onto Straight Lines
Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit...
-
Two-Step Coloring of Grid Graphs of Different Types
AbstractIn this article, we consider the NP-hard problem of the two-step coloring of a graph. It is required to color the graph in the given number...
-
Efficiently Enumerating All Spanning Trees of a Plane 3-Tree
A spanning tree T of a connected, undirected graph G is an acyclic subgraph having all vertices and a minimal number of edges of G connecting those...
-
Flip** Plane Spanning Paths
Let S be a planar point set in general position, and let \(\mathcal {P}(S)\)...
-
Star-Forest Decompositions of Complete Graphs
We deal with the problem of decomposing a complete geometric graph into plane star-forests. In particular, we disprove a recent conjecture by Pach,...
-
Succinct Permutation Graphs
We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal...
-
The Rique-Number of Graphs
We continue the study of linear layouts of graphs in relation to known data structures. At a high level, given a data structure, the goal is to find...
-
-
A Logarithmic Bound for Simultaneous Embeddings of Planar Graphs
A set \(\mathcal {G}\) of planar graphs on the...