Accepted Papers
Invited Presentations
Speaker:
Title: Topological aspects of random graphs
Abstract: In this talk we will discuss various topological aspects of random graphs. How does the genus of a uniform random graph change as the number of edges increases? How does a topological constraint (such as being planar or imposing an upper bound on the genus) influence the structure of a random graph (such as the order of the largest component, the length of the shortest and longest cycles)?
Contributed Presentations
Click on the title of the paper to show the abstract.

On the complexity of finding large odd induced subgraphs and odd colorings
Abstract: We study the complexity of the problems of finding, given a graph G, a largest induced subgraph of G with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition V(G). We call these parameters mos(G) and χ_{odd}(G), respectively. We prove that deciding whether χ_{odd}(G) ≤ q is polynomialtime solvable if q ≤ 2, and NPcomplete otherwise. We provide algorithms in time 2^{O(rw)} · n^{O(1)} and 2^{O(q · rw)} · n^{O(1)} to compute mos(G) and to decide whether χ_{odd}(G) ≤ q on nvertex graphs of rankwidth at most rw, respectively, and we prove that the dependency on rankwidth is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

Characterization and Lineartime Recognition of Paired Threshold Graphs
Abstract: In a paired threshold graph, each vertex has a weight, and two vertices are adjacent if and only if their weight sum is large enough and their weight difference is small enough. The class of paired threshold graphs generalizes threshold graphs and unit interval graphs, both very well studied. We present a vertex ordering characterization of this graph class, which enables us to prove that it is a subclass of interval graphs. Further study of clique paths of paired threshold graphs leads to a simple lineartime recognition algorithm for this graph class.

On flips in planar matchings
Abstract: In this paper we investigate the structure of flip graphs on noncrossing perfect matchings in the plane. Consider all noncrossing straightline perfect matchings on a set of 2n points that are placed equidistantly on the unit circle. The graph H_{n} has those matchings as vertices, and an edge between any two matchings that differ in replacing two matching edges that span an empty quadrilateral with the other two edges of the quadrilateral, provided that the quadrilateral contains the center of the unit circle.
We show that the graph H_{n} is connected for odd n, but has exponentially many small connected components for even n, which we characterize and count via Catalan and generalized Narayana numbers. For odd n, we also prove that the diameter of H_{n} is at least linear and at most loglinear in n. Furthermore, we determine the minimum and maximum degree of H_{n} for all n, and characterize and count the corresponding vertices. Our results imply the nonexistence of certain rainbow cycles, and they answer several open questions and conjectures raised in a recent paper by Felsner, Kleist, Mütze, and Sering. 
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
Abstract: For many algorithmic problems on graphs of treewidth tw, a standard dynamic programming approach gives an algorithm with time and space complexity 2^{O(tw)}n^{O(1)}. It turns out that when one considers a more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form 2^{O(td)}n^{O(1)}, where td is the treedepth. This transfer of methodology is, however, far from being automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity 2^{O(tw log(tw))}n^{O(1)} on graphs of treewidth tw, but it is not clear how to convert them into timeefficient polynomial space algorithms for graphs of low treedepth.
Cygan et al. (FOCS'11) introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity 2^{O(tw)} n^{O(1)}. Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time 2^{O(td)}n^{O(1)} and polynomial space usage. However, a number of important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path.
In this paper we clarify the situation by showing that Hamiltonian Cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit 5^{td} n^{O(1)}time and polynomial space algorithms on graphs of treedepth td. The algorithms are randomized Monte Carlo with only false negatives. 
Wellpartitioned chordal graphs: obstruction set and disjoint paths
Abstract: We introduce a new subclass of chordal graphs that generalizes split graphs, which we call wellpartitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Wellpartitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We provide a characterization of wellpartitioned chordal graphs by forbidden induced subgraphs, and give a polynomialtime algorithm that given any graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is wellpartitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices is in FPT parameterized by k on wellpartitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we observe that there are problems that are polynomialtime solvable on split graphs, but become NPcomplete on wellpartitioned chordal graphs.

Knot Diagrams of Treewidth Two
Abstract: In this paper, we study knot diagrams for which the underlying graph has treewidth two. We give a linear time algorithm for the following problem: given a knot diagram of treewidth two, does it represent the trivial knot?
We also show that for a link diagram of treewidth two we can test in linear time if it represents the unlink. From the algorithm, it follows that a diagram of the trivial knot of treewidth 2 can always be reduced to the trivial diagram with at most n untwist and unpoke Reidemeister moves. 
CliqueWidth of Point Configurations
Abstract: While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of cliquewidth to geometric point configurations represented by their order type. We study basic properties of this cliquewidth notion, and relate it to the monadic secondorder logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NPhard in general, in the special case that the input point set is of bounded cliquewidth and the cliquewidth expression is also given.

Degree Distribution for DuplicationDivergence Graphs: Large Deviations
Abstract: We present a rigorous and precise analysis of the degree distribution in a dynamic graph model introduced by Solé et al. in which nodes are added according to a duplicationdivergence mechanism, i.e.by iteratively copying a node and then randomly inserting and deleting some edges for a copied node. This graph model finds many applications since it well captures the growth of some realworld processes e.g. biological or social networks. However, there are only a handful of rigorous results concerning this model. In this paper we present rigorous results concerning the degree distribution. We focus on two related problems: the expected value and large deviation for the degree of a fixed node through the evolution of the graph and the expected value and large deviation of the average degree in the graph. We present exact and asymptotic results showing that both quantities may decrease or increase over time depending on the model parameters. Our findings are a step towards a better understanding of the overall graph behaviors, especially, degree distribution, symmetry, and compression, important open problems in this area.

Parameterized Inapproximability of Independent Sets in HFree Graphs
Abstract: We study the Independent Set problem in Hfree graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomialtime and parameterized algorithms. Halldórsson [SODA 1995] showed that for every δ>0 the IS problem has a polynomialtime ((d1)/2+δ)approximation algorithm in K_{1,d}free graphs. We extend this result by showing that K_{a,b}free graphs admit a polynomialtime α(G)^{11/a}approximation, where α(G) is the size of a maximum independent set in G. Furthermore, we complement the result of Halldórsson by showing that for some γ=Θ(d ·log d), there is no polynomialtime γapproximation algorithm for these graphs, unless NP = ZPP. For every graph H that is (1) a cycle of constant length at least 4, (2) the star K_{1,4}, or (3) any tree with two vertices of degree at least 3 at constant distance, Bonnet et al. [IPEC 2018] showed that IS is W[1]hard on Hfree graphs parameterized by the size k of the independent set. We strengthen this result by proving three inapproximability results for Hfree graphs based on different complexity assumptions: first, under the ETH, there is no f(k) · n^{o(k/ log k)} algorithm for any computable function f. Then, under the deterministic GapETH, there is a constant δ>0 such that no δapproximation can be computed in f(k) · n^{O(1)} time. Also, under the stronger randomized GapETH there is no such algorithm with runtime f(k) · n^{o(k)}. Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, Independent Set has no n^{o(α(H))} algorithm in Hfree graphs. Also, we prove that there is no d/k^{o(1)}approximation algorithm for K_{1,d}free graphs with runtime f(d,k) · n^{O(1)}, under the deterministic GapETH.

Drawing Graphs as Spanners
Abstract: We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph G, the goal is to construct a straightline drawing \Gamma of G in the plane such that, for any two vertices u and v of G, the ratio between the minimum length of any path from u to v and the Euclidean distance between u and v is small. The maximum such ratio, over all pairs of vertices of G, is the spanning ratio of Γ. First, we show that deciding whether a graph admits a straightline drawing with spanning ratio 1, a proper straightline drawing with spanning ratio 1, and a planar straightline drawing with spanning ratio 1 are NPcomplete, ∃ℝcomplete, and lineartime solvable problems, respectively. Second, we prove that, for every ε>0, every (planar) graph admits a proper (resp. planar) straightline drawing with spanning ratio smaller than 1+ε. Third, we note that our drawings with spanning ratio smaller than 1+ε have large edgelength ratio, that is, the ratio between the lengths of the longest and of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straightline drawings with constant spanning ratio and polynomial edgelength ratio from graphs that do not.

Feedback Edge Sets in Temporal Graphs
Abstract: The classical, lineartime solvable Feedback Edge Set problem is concerned with finding a minimum number of edges intersecting all cycles in a (static, unweighted) graph. We provide a first study of this problem in the setting of temporal graphs, where edges are present only at certain points in time. We find that there are four natural generalizations of Feedback Edge Set, all of which turn out to be NPhard. We also study the tractability of these problems with respect to several parameters (solution size, lifetime, and number of graph vertices, among others) and obtain some parameterized hardness but also fixedparameter tractability results.

Finding large matchings in 1planar graphs of minimum degree 3
Abstract: A matching is a set of edges without common endpoint. It was recently shown that every 1planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per edge) that has minimum degree 3 has a matching of size at least (n+12)/7, and this is tight for some graphs. The proof did not come with an algorithm to find the matching more efficiently than a generalpurpose maximummatching algorithm. In this paper, we give such an algorithm. More generally, we show that any matching that has no augmenting paths of length 9 or less has size at least (n+12)/7 in a 1planar graph with minimum degree 3.

Stable networks and connected safe set problem
Abstract: Let G be a graph, and let w be a nonnegative realvalued weight function on V(G). For every subset X of V(G), let w(X)=Σ_{v ∈ X} w(v). A nonempty subset S ⊂ V(G) is a weighted safe set of (G,w) if, for every component C of the subgraph induced by S and every component D of GS, we have w(C) ≥ w(D) whenever there is an edge between C and D. If the subgraph of G induced by a weighted safe set S is connected, then the set S is called a connected weighted safe set of (G,w). The weighted safe number s(G,w) and connected weighted safe number cs(G,w) of (G,w) are the minimum weights w(S) among all weighted safe sets and all connected weighted safe sets of (G,w), respectively. It is easy to see that for every pair (G,w), s(G,w) ≤ cs(G,w) by their definitions. In [Journal of Combinatorial Optimization, 37:685701, 2019], the authors asked which pair (G,w) satisfies the equality and it was shown that every weighted cycle satisfies the equality. In the companion paper [European Journal of Combinatorics, in press] of this paper, we give a complete list of connected bipartite graphs G such that s(G,w)=cs(G,w) for every weight function w on V(G). In this paper, as is announced in the companion paper, we show that, for any graph G in this list and for any nonnegative vertexweight function w of G, there exists an FPTAS for calculating a minimum connected safe set of the pair (G,w). In order to prove this result, we also prove that, for any tree T and for any nonnegative vertexweight function w^{p} of T, there exists an FPTAS for calculating a minimum connected safe set of the pair (T,w^{p}). This gives a complete answer to a question posed by Bapat et al. [Networks, 71:8292, 2018]. We also show that determining whether a graph is in the above list or not can be done in linear time.

Strong cliques in diamondfree graphs
Abstract: A strong clique in a graph is a clique intersecting all inclusionmaximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamondfree graphs, from both structural and algorithmic points of view. We show that the following five NPhard problems all remain NPhard when restricted to the class of diamondfree graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following two problems whose computational complexity is open in general can be solved in linear time in the class of diamondfree graphs: Is every maximal clique strong? Is every edge contained in a strong clique? These results are derived from a characterization of diamondfree graphs in which every maximal clique is strong, which also implies an improved ErdősHajnal property for such graphs. 
On Finding Balanced Bicliques via Matchings
Abstract: In the Maximum Balanced Biclique Problem (MBB), we are given an nvertex graph G=(V,E), and the goal is to find a balanced complete bipartite subgraph with q vertices on each side, while maximizing q. The MBB problem is among the first known NPhard problem which is recently shown to be n^{1o(1)}hard to approximate, assuming the Small Set Expansion hypothesis [Manurangsi, ICALP 2017]. An O(n·log n) approximation follows from a simple bruteforce enumeration argument. In this paper, we provide the first approximation guarantees beyond bruteforce: (1) an O(n·log^{2} n) efficient approximation algorithm, and (2) a parameterized approximation that returns, for any positive integer r, an rapproximation algorithm in time exp(O(n/(r·log r))). To obtain these results, we translate the subgraph removal arguments of [Feige, SIDMA 2004] in the context of finding a clique into one that finds a balanced biclique. Key to our proof is the use of matching edges to guide the search of a balanced biclique.

2.5Connectivity: Unique Components, Critical Graphs, and Applications
Abstract: If a 2connected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5connected. We prove that every 2connected graph has a canonical decomposition into 2.5connected components. These components are arranged in a treestructure. We also discuss the connection between 2.5connected components and triconnected components and use this to present a linear time algorithm which computes the 2.5connected components of a graph. We show that every critical 2.5connected graph other than a complete graph on four vertices can be obtained from critical 2.5connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5connected components in the context of cycle decompositions and cycle packings.

Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mimwidth
Abstract: The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects all cycles containing a vertex of a given set. We design a metaalgorithm that will allow to solve both problems in time 2^{O(rw3)}·n^{4}, 2^{O(q2·log(q))}·n^{4}, and n^{O(k2)} where rw is the rankwidth, q the ℚrankwidth, and k the mimwidth of a given decomposition. This answers in the affirmative an open question raised by Jaffke et al. (Algorithmica, 2019) concerning an XP algorithm for SFVS parameterized by mimwidth. By a unified algorithm, this solves both problems in polynomialtime on the following graph classes: Interval, Permutation, and BiInterval graphs, Circular Arc and Circular, Permutation graphs, Convex graphs, kPolygon, Dilworthk and CokDegenerate graphs for fixed k; and also on Leaf Power graphs if a leaf root is given as input, on HGraphs for fixed H if an Hrepresentation is given as input, and on arbitrary powers of graphs in all of the above classes. Prior to our results, only SFVS was known to be tractable restricted only on Interval and Permutation graphs, whereas all other results are new.

Treewidth versus clique number in graph classes with a forbidden structure
Abstract: Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call (tw,ω)bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and kcoloring problems. We consider six wellknown graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs H for which the class of graphs excluding H is (tw,ω)bounded. Our results imply that the class of 1perfectly orientable graphs is (tw,ω)bounded, answering a question of Brešar, Hartinger, Kos, and Milanič from 2018. We also reveal some further algorithmic applications of (tw,ω)bounded graph classes related to clique and kcoloring problems.

LinearTime Recognition of DoubleThreshold Graphs
Abstract: A graph G = (V,E) is a doublethreshold graph if there exist a vertexweight function w : V → ℝ and two real numbers lb, ub ∈ ℝ such that uv ∈ E if and only if lb ≤ w(u) + w(v) ≤ ub. In the literature, those graphs are studied as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of doublethreshold graphs, which gives connections to bipartite permutation graphs. Using the new characterization, we present a lineartime algorithm for recognizing doublethreshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [COCOON 2018] ran in O(n^{6}) time,

Edge elimination and weighted graph classes
Abstract: Edgeweighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from an edgeweighted graph by removing all sufficiently light edges. This naturally leads to a generalization of the concept of a graph class to the weighted case by requiring that all level graphs belong to the class. We examine some types of monotonicity of graph classes, such as sandwich monotonicity, to construct edge elimination schemes of edgeweighted graphs. This leads to lineartime recognition algorithms of weighted graphs for which all level graphs are split, threshold, or chain graphs.

Bitonic storderings for Upward Planar Graphs: The Variable Embedding Setting
Abstract: Bitonic storderings for stplanar graphs were recently introduced as a method to cope with several graph drawing problems. Notably, they have been used to obtain the bestknown upper bound on the number of bends for upward planar polyline drawings with at most one bend per edge. For an stplanar graph that does not admit a bitonic stordering, one may split certain edges such that for the resulting graph such an ordering exists. Since each split is interpreted as a bend, one is usually interested in splitting as few edges as possible. While this optimization problem admits a lineartime algorithm in the fixed embedding setting, it remains open in the variable embedding setting. We close this gap in the literature by providing a lineartime algorithm that optimizes over all embeddings of the input stplanar graph. The bestknown lower bound on the number of required splits of an stplanar graph with n vertices is n3. However, it is possible to compute a bitonic stordering without any split for the stplanar graph obtained by reversing the orientation of all edges. In terms of upward planar polyline drawings, the former translates into n3 bends, while the latter into no bends. We show that this idea cannot always be exploited by describing an stplanar graph that needs at least n5 splits in both orientations.

Guarding Quadrangulations and Stacked Triangulations with Edges
Abstract: Let G=(V,E) be a plane graph. A face f of G is guarded by an edge vw if at least one vertex from v,w is on the boundary of f. For a planar graph class C we ask for the minimal number of edges needed to guard all faces of any nvertex graph in C. We prove that n/3 edges are always sufficient for quadrangulations and give a construction where (n2)/4 edges are necessary. For 2degenerate quadrangulations we improve this to a tight upper bound of n/4 edges. We further prove that 2n/7 edges are always sufficient for stacked triangulations (that are the 3degenerate triangulations) and show that this is best possible up to a small additive constant.

Weighted Additive Spanners
Abstract: A spanner of a graph G is a subgraph H that approximately preserves shortest path distances in G. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured multiplicatively. In this work, we investigate whether one can similarly extend constructions of spanners with purely additive error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic +2 and +4 unweighted spanners (both allpairs and pairwise) to +2W and +4W weighted spanners, where W is the maximum edge weight. For a technical reason, the +6 unweighted spanner becomes a +8W weighted spanner; closing this error gap is an interesting remaining open problem.

CliqueWidth: Harnessing the Power of Atoms
Abstract: Many NPcomplete graph problems are polynomially solvable on graph classes of bounded cliquewidth. Several of these problems are polynomially solvable on a hereditary graph class 𝒢 if they are so on the atoms (graphs with no clique cutset) of 𝒢. Hence, we initiate a systematic study into boundedness of cliquewidth of atoms of hereditary graph classes. A graph G is Hfree if H is not an induced subgraph of G, and G is (H_{1},H_{2})free if it is both H1free and H_{2}free. A class of Hfree graphs has bounded cliquewidth if and only its atoms have this property. This is no longer true for (H_{1},H_{2})free graphs as evidenced by one known example. We prove the existence of another such pair (H_{1},H_{2}) and classify the boundedness of (H_{1},H_{2})free atoms for all but 22 cases.

Universal Geometric Graphs
Abstract: We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some subclass of planar graphs; a geometric graph is universal for a class ℋ of planar graphs if it contains an embedding, i.e., a crossingfree drawing, of every graph in ℋ. Our main result is that there exists a geometric graph with n vertices and O(n·log n) edges that is universal for nvertex forests; this extends to the geometric setting a wellknown graphtheoretic result by Chung and Graham, which states that there exists an nvertex graph with O(n·log n) edges that contains every nvertex forest as a subgraph. Our O(n·log n) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0, every nvertex convex geometric graph that is universal for nvertex outerplanar graphs has a nearquadratic number of edges, namely Ω_{h}(n^{21/h}); this almost matches the trivial O(n^{2}) bound given by the nvertex complete convex geometric graph. Finally, we prove that there is an nvertex convex geometric graph with n vertices and O(n·log n) edges that is universal for nvertex caterpillars.

Inserting one edge into a simple drawing is hard
Abstract: A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi's Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NPcomplete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles 𝒜 and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φ_{σ} extending σ for which 𝒜 ∪ Φ_{σ} is again an arrangement of pseudocircles.

The linear arboricity conjecture for 3degenerate graphs
Abstract: A klinear coloring of a graph G is an edge coloring of G with k colors so that each color class forms a linear foresta forest whose each connected component is a path. The linear arboricity χ_{l}'(G) of G is the minimum integer k such that there exists a klinear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, χ_{l}'(G) ≤ ⌈(Δ(G)+1)/2⌉ where Δ(G) is the maximum degree of G.
We prove the conjecture for 3degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture for trianglefree planar graphs. Our proof also yields an O(n)time algorithm that partitions the edge set of any 3degenerate graph G on n vertices into at most ⌈(Δ(G)+1)/2⌉ linear forests. Since for any graph G, χ_{l}'(G)≥⌈(Δ(G))/2⌉, the partition produced by the algorithm differs from the optimum by at most an additive factor of 1. 
Computing Subset Transversals in HFree Graphs
Abstract: We study the computational complexity of two wellknown graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to Hfree graphs, that is, to graphs that do not contain some fixed graph H as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on Hfree graphs for every graph H except when H=sP_{1}+P_{4} for some s≥1. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomialtime solvable for (sP_{1}+P_{4})free graphs for every s≥1.

Recognizing kClique Extendible Orderings
Abstract: We consider the complexity of recognizing kcliqueextendible graphs (kCE graphs) introduced by Spinrad (Efficient Graph Representations, AMS 2003), which are generalizations of comparability graphs. A graph is kcliqueextendible if there is an ordering of the vertices such that whenever two ksized overlapping cliques A and B have k1 common vertices, and these common vertices appear between the two vertices a,b∈ (A\B)∪(B\A) in the ordering, there is an edge between a and b, implying that A ∪ B is a (k+1)sized clique. Such an ordering is said to be a kCE ordering. These graphs arise in applications related to modelling the preference relations. Recently, it has been shown that finding a maximum sized clique in such a graph with m edges can be found in O(m^{O(k)}) time [Hamburger et al. 2017]. When k is 2, such graphs are precisely the wellknown class of comparability graphs and when k is 3 they are called triangleextendible graphs. It has been shown that triangleextendible graphs appear as induced subgraphs of visibility graphs of a simple polygon, and the complexity of recognizing them has been mentioned as an open problem in literature. While comparability graphs (i.e. 2CE graphs) can be recognized in polynomial time, we show that recognizing kCE graphs is NPhard for any fixed k ≥ 3 and coNPhard when k is part of the input. While our reduction for k ≥ 4 is from the betweenness problem, for k=3, our reduction is an intricate one from the 3colouring problem. We also show that
 determining whether a given ordering of the vertices of a graph is a kCE ordering, and
 finding an lsized (or maximum sized) clique in a kCE graph, given a kCE ordering
are complete for the parameterized complexity class W[1] when parameterized by k. However we show that the former is fixedparameter tractable when parameterized by the treewidth of the graph.

Graph Isomorphism Restricted by Lists
Abstract: The complexity of graph isomorphism (GI) is a famous unresolved problem in theoretical computer science. For graphs G and H, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (LGI) is NPcomplete: for each u ∈ V(G), we are given a list L(u) ⊆ V(H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GI can be used to solve LGI. We prove the following:
1) When GI is GIcomplete for a class of graphs, it usually implies NPcompleteness of LGI.
2) Several combinatorial algorithms for GI can be modified into algorithms for LGI: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs, and bounded treewidth graphs.
3) Two basic algorithms based on group theory cannot be modified: LGI remains NPcomplete for cubic colored graphs with sizes of color classes bounded by 8. 
Plattenbauten: Touching Rectangles in Space
Abstract: Planar bipartite graphs can be represented as touching graphs of horizontal and vertical segments in ℝ^{2}. We study a generalization in space, namely, touching graphs of axisaligned rectangles in ℝ^{3}. We prove that planar 3colorable graphs are touching graphs of axisaligned rectangles in ℝ^{3}, the result implies a characterization of corner polytopes previously obtained by Eppstein and Mumford. A byproduct of our proof is a distributive lattice structure on the set of orthogonal surfaces with given skeleton. Moreover, we study the subclass of strong representations, i.e., families of axisaligned rectangles in ℝ^{3} in general position such that all regions are boxes. We show that the resulting graphs correspond to octahedrations of an octahedron. This generalizes the correspondence between planar quadrangulations and families of horizontal and vertical segments in ℝ^{2} with the property that all regions are rectangles.

Combinatorial Bounds for Conflictfree Coloring on Open Neighborhoods
Abstract: In an undirected graph G, a conflictfree coloring with respect to open neighborhoods (denoted by CFON coloring) is an assignment of colors to the vertices such that every vertex has a uniquely colored vertex in its open neighborhood. The minimum number of colors required for a CFON coloring of G is the CFON chromatic number of G, denoted by χ_{ON}(G).
The decision problem that asks whether χ_{ON}(G) ≤ k is NPcomplete. Structural as well as algorithmic aspects of this problem have been well studied. We obtain the following results for χ_{ON}(G):
– Bodlaender, Kolay and Pieterse [WADS 2019] showed the upper bound χ_{ON}(G) ≤ fvs(G) +3, where fvs(G) denotes the size of a minimum feedback vertex set of G. We show the improved bound of χ_{ON}(G) ≤ fvs(G) + 2, which is tight, thereby answering an open question in the above paper.
– We study the relation between χ_{ON}(G) and the pathwidth of the graph G, denoted pw(G). The above paper from WADS 2019 showed the upper bound χ_{ON}(G) ≤ 2tw(G) + 1 where tw(G) stands for the treewidth of G. This implies an upper bound of χ_{ON}(G) ≤ 2pw(G)+ 1. We show an improved bound of χ_{ON}(G) ≤ 5/3 (pw(G) + 1).
– We prove new bounds for χ_{ON}(G) with respect to the structural parameters neighborhood diversity and distance to cluster, improving the existing results of Gargano and Rescigno [Theor. Comput. Sci. 2015] and Reddy [Theor. Comput. Sci. 2018], respectively. Furthermore, our techniques also yield improved bounds for the closed neighborhood variant of the problem.
– We also study the partial coloring variant of the CFON coloring problem, which allows vertices to be left uncolored. Let χ*_{ON}(G) denote the minimum number of colors required to color G as per this variant. Abel et. al. [SIDMA 2018] studied this version of the problem and showed that χ*_{ON}(G)≤ 8 when G is planar. They asked if fewer colors would suffice for planar graphs. We answer this question by showing that χ*_{ON}(G) ≤ 5 for all planar G. This approach also yields the bound χ*_{ON}(G) ≤ 4 for all outerplanar G.
All our bounds are a result of constructive algorithmic procedures.