![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Finding Geometric Representations of Apex Graphs is NP-Hard
Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin & Gonçalves, SODA 2009), L-shapes (Gonçalves et a...
-
Chapter and Conference Paper
s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs
In this paper, we study the computational complexity of s -Club Cluster Vertex Deletion. Given a graph, s -Club Cluster Vertex Deletion (s -CVD) aims to delete the minimum number of vertices from the graph so th...
-
Chapter and Conference Paper
Algorithms and Complexity of s-Club Cluster Vertex Deletion
An s-club is a graph which has diameter at most s. Let G be a graph. A set of vertices \(D\subseteq V(G)\) ...
-
Chapter and Conference Paper
Approximating Minimum Dominating Set on String Graphs
A string graph is an intersection graph of simple curves on the plane. For \(k\ge 0\) ,
-
Chapter and Conference Paper
Dominating Set on Overlap Graphs of Rectangles Intersecting a Line
A graph \(G = (V, E)\) is called a rectangle overlap graph if there is a bijection between V and a set ...
-
Chapter and Conference Paper
On Rectangle Intersection Graphs with Stab Number at Most Two
Rectangle intersection graphs are the intersection graphs of axis-parallel rectangles in the plane. A graph G is said to be a k-stabbable rectangle intersection graph, or k-SRIG for short, if it has a rectangle i...
-
Chapter and Conference Paper
On a Special Class of Boxicity 2 Graphs
We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectangle intersection graph where ...