Skip to main content

Accepted Papers

Invited Presentations

Speaker: Mihyun Kang (TU Graz)
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.

  • Rémy Belmonte and Ignasi Sau. 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 polynomial-time solvable if q ≤ 2, and NP-complete otherwise. We provide algorithms in time 2O(rw) · nO(1) and 2O(q · rw) · nO(1) to compute mos(G) and to decide whether χodd(G) ≤ q on n-vertex graphs of rank-width at most rw, respectively, and we prove that the dependency on rank-width 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.

  • Yixin Cao, Guozhen Rong and Jianxin Wang. Characterization and Linear-time 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 linear-time recognition algorithm for this graph class.

  • Marcel Milich, Torsten Mütze and Martin Pergel. On flips in planar matchings

    Abstract: In this paper we investigate the structure of flip graphs on non-crossing perfect matchings in the plane. Consider all non-crossing straight-line perfect matchings on a set of 2n points that are placed equidistantly on the unit circle. The graph Hn 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 Hn 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 Hn is at least linear and at most log-linear in n. Furthermore, we determine the minimum and maximum degree of Hn for all n, and characterize and count the corresponding vertices. Our results imply the non-existence of certain rainbow cycles, and they answer several open questions and conjectures raised in a recent paper by Felsner, Kleist, Mütze, and Sering.

  • Jesper Nederlof, Michał Pilipczuk, Céline Swennenhuis and Karol Węgrzycki. 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 2O(tw)nO(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 2O(td)nO(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 2O(tw log(tw))nO(1) on graphs of treewidth tw, but it is not clear how to convert them into time-efficient 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 2O(tw) nO(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 2O(td)nO(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 5td nO(1)-time and polynomial space algorithms on graphs of treedepth td. The algorithms are randomized Monte Carlo with only false negatives.

  • Jungho Ahn, Lars Jaffke, O-Joung Kwon and Paloma de Lima. Well-partitioned chordal graphs: obstruction set and disjoint paths

    Abstract: We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned 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. Well-partitioned 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 well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given any graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned 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 well-partitioned 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 polynomial-time solvable on split graphs, but become NP-complete on well-partitioned chordal graphs.

  • Hans L. Bodlaender, Benjamin A. Burton, Fedor Fomin and Alexander Grigoriev. 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.

  • Onur Çağırıcı, Petr Hlineny, Filip Pokrývka and Abhisekh Sankaran. Clique-Width 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 clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and relate it to the monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given.

  • Alan Frieze, Krzysztof Turowski and Wojciech Szpankowski. Degree Distribution for Duplication-Divergence 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 duplication-divergence 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 real-world 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.

  • Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai and Paweł Rzążewski. Parameterized Inapproximability of Independent Sets in H-Free Graphs

    Abstract: We study the Independent Set problem in H-free graphs, i.e., graphs excluding some fixed graph H as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms. Halldórsson [SODA 1995] showed that for every δ>0 the IS problem has a polynomial-time ((d-1)/2+δ)-approximation algorithm in K1,d-free graphs. We extend this result by showing that Ka,b-free graphs admit a polynomial-time α(G)1-1/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 polynomial-time γ-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 K1,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 H-free graphs parameterized by the size k of the independent set. We strengthen this result by proving three inapproximability results for H-free graphs based on different complexity assumptions: first, under the ETH, there is no f(k) · no(k/ log k) algorithm for any computable function f. Then, under the deterministic Gap-ETH, there is a constant δ>0 such that no δ-approximation can be computed in f(k) · nO(1) time. Also, under the stronger randomized Gap-ETH there is no such algorithm with runtime f(k) · no(k). Finally, we consider the parameterization by the excluded graph H, and show that under the ETH, Independent Set has no no(α(H)) algorithm in H-free graphs. Also, we prove that there is no d/ko(1)-approximation algorithm for K1,d-free graphs with runtime f(d,k) · nO(1), under the deterministic Gap-ETH.

  • Oswin Aichholzer, Manuel Borrazzo, Prosenjit Bose, Jean Cardinal, Fabrizio Frati, Pat Morin and Birgit Vogtenhuber. 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 straight-line 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 straight-line drawing with spanning ratio 1, a proper straight-line drawing with spanning ratio 1, and a planar straight-line drawing with spanning ratio 1 are NP-complete, ∃ℝ-complete, and linear-time solvable problems, respectively. Second, we prove that, for every ε>0, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than 1+ε. Third, we note that our drawings with spanning ratio smaller than 1+ε have large edge-length 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 straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that do not.

  • Roman Haag, Hendrik Molter, Rolf Niedermeier and Malte Renken. Feedback Edge Sets in Temporal Graphs

    Abstract: The classical, linear-time 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 NP-hard. 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 fixed-parameter tractability results.

  • Therese Biedl and Fabian Klute. Finding large matchings in 1-planar graphs of minimum degree 3

    Abstract: A matching is a set of edges without common endpoint. It was recently shown that every 1-planar 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 general-purpose maximum-matching 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 1-planar graph with minimum degree 3.

  • Shinya Fujita, Boram Park and Tadashi Sakuma. Stable networks and connected safe set problem

    Abstract: Let G be a graph, and let w be a non-negative real-valued weight function on V(G). For every subset X of V(G), let w(X)=Σv ∈ X w(v). A non-empty 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 G-S, 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:685-701, 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 non-negative vertex-weight 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 non-negative vertex-weight function wp of T, there exists an FPTAS for calculating a minimum connected safe set of the pair (T,wp). This gives a complete answer to a question posed by Bapat et al. [Networks, 71:82-92, 2018]. We also show that determining whether a graph is in the above list or not can be done in linear time.

  • Nina Chiarelli, Berenice Martínez-Barona, Martin Milanič, Jérôme Monnot and Peter Muršič. Strong cliques in diamond-free graphs

    Abstract: A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard problems all remain NP-hard when restricted to the class of diamond-free 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 diamond-free graphs: Is every maximal clique strong? Is every edge contained in a strong clique? These results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.

  • Parinya Chalermsook, Wanchote Jiamjitrak and Ly Orgo. On Finding Balanced Bicliques via Matchings

    Abstract: In the Maximum Balanced Biclique Problem (MBB), we are given an n-vertex 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 NP-hard problem which is recently shown to be n1-o(1)-hard to approximate, assuming the Small Set Expansion hypothesis [Manurangsi, ICALP 2017]. An O(n·log n) approximation follows from a simple brute-force enumeration argument. In this paper, we provide the first approximation guarantees beyond brute-force: (1) an O(n·log2 n) efficient approximation algorithm, and (2) a parameterized approximation that returns, for any positive integer r, an r-approximation 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.

  • Irene Heinrich, Till Heller, Eva Schmidt and Manuel Streicher. 2.5-Connectivity: Unique Components, Critical Graphs, and Applications

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

  • Benjamin Bergougnoux, Charis Papadopoulos and Jan Arne Telle. Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width

    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 meta-algorithm that will allow to solve both problems in time 2O(rw3)·n4, 2O(q2·log(q))·n4, and nO(k2) where rw is the rank-width, q the ℚ-rank-width, and k the mim-width 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 mim-width. By a unified algorithm, this solves both problems in polynomial-time on the following graph classes: Interval, Permutation, and Bi-Interval graphs, Circular Arc and Circular, Permutation graphs, Convex graphs, k-Polygon, Dilworth-k and Co-k-Degenerate graphs for fixed k; and also on Leaf Power graphs if a leaf root is given as input, on H-Graphs for fixed H if an H-representation 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.

  • Clément Dallard, Martin Milanič and Kenny Štorgel. 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 k-coloring problems. We consider six well-known 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 1-perfectly 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 k-coloring problems.

  • Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi and Yushi Uno. Linear-Time Recognition of Double-Threshold Graphs

    Abstract: A graph G = (V,E) is a double-threshold graph if there exist a vertex-weight 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 double-threshold graphs, which gives connections to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [COCOON 2018] ran in O(n6) time,

  • Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač, Robert Scheffler and Martin Strehler. Edge elimination and weighted graph classes

    Abstract: Edge-weighted 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 edge-weighted 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 edge-weighted graphs. This leads to linear-time recognition algorithms of weighted graphs for which all level graphs are split, threshold, or chain graphs.

  • Patrizio Angelini, Michael Bekos, Henry Förster and Martin Gronemann. Bitonic st-orderings for Upward Planar Graphs: The Variable Embedding Setting

    Abstract: Bitonic st-orderings for st-planar graphs were recently introduced as a method to cope with several graph drawing problems. Notably, they have been used to obtain the best-known upper bound on the number of bends for upward planar polyline drawings with at most one bend per edge. For an st-planar graph that does not admit a bitonic st-ordering, 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 linear-time algorithm in the fixed embedding setting, it remains open in the variable embedding setting. We close this gap in the literature by providing a linear-time algorithm that optimizes over all embeddings of the input st-planar graph. The best-known lower bound on the number of required splits of an st-planar graph with n vertices is n-3. However, it is possible to compute a bitonic st-ordering without any split for the st-planar graph obtained by reversing the orientation of all edges. In terms of upward planar polyline drawings, the former translates into n-3 bends, while the latter into no bends. We show that this idea cannot always be exploited by describing an st-planar graph that needs at least n-5 splits in both orientations.

  • Paul Jungeblut and Torsten Ueckerdt. 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 n-vertex graph in C. We prove that n/3 edges are always sufficient for quadrangulations and give a construction where (n-2)/4 edges are necessary. For 2-degenerate 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 3-degenerate triangulations) and show that this is best possible up to a small additive constant.

  • Richard Spence, Abu Reyan Ahmed, Stephen Kobourov, Faryad Darabi Sahneh and Greg Bodwin. 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 all-pairs 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.

  • Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniel Paulusma and Pawel Rzążewski. Clique-Width: Harnessing the Power of Atoms

    Abstract: Many NP-complete graph problems are polynomially solvable on graph classes of bounded clique-width. Several of these problems are polynomially solvable on a hereditary graph class 𝒢 if they are so on the atoms (graphs with no clique cut-set) of 𝒢. Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph G is H-free if H is not an induced subgraph of G, and G is (H1,H2)-free if it is both H1-free and H2-free. A class of H-free graphs has bounded clique-width if and only its atoms have this property. This is no longer true for (H1,H2)-free graphs as evidenced by one known example. We prove the existence of another such pair (H1,H2) and classify the boundedness of (H1,H2)-free atoms for all but 22 cases.

  • Fabrizio Frati, Michael Hoffmann and Csaba Toth. 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 sub-class of planar graphs; a geometric graph is universal for a class ℋ of planar graphs if it contains an embedding, i.e., a crossing-free 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 n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(n·log n) edges that contains every n-vertex 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 n-vertex convex geometric graph that is universal for n-vertex outerplanar graphs has a near-quadratic number of edges, namely Ωh(n2-1/h); this almost matches the trivial O(n2) bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(n·log n) edges that is universal for n-vertex caterpillars.

  • Alan Arroyo, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber and Tilo Wiedera. 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 NP-complete 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.

  • Manu Basavaraju, Arijit Bishnu, Mathew Francis and Drimit Pattanayak. The linear arboricity conjecture for 3-degenerate graphs

    Abstract: A k-linear coloring of a graph G is an edge coloring of G with k colors so that each color class forms a linear forest---a 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 k-linear 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 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture for triangle-free planar graphs. Our proof also yields an O(n)-time algorithm that partitions the edge set of any 3-degenerate 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.

  • Matthew Johnson, Nick Brettell, Giacomo Paesani and Daniel Paulusma. Computing Subset Transversals in H-Free Graphs

    Abstract: We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free 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 H-free graphs for every graph H except when H=sP1+P4 for some s≥1. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for (sP1+P4)-free graphs for every s≥1.

  • Rian Neogi, Venkatesh Raman and Mathew Francis. Recognizing k-Clique Extendible Orderings

    Abstract: We consider the complexity of recognizing k-clique-extendible graphs (k-C-E graphs) introduced by Spinrad (Efficient Graph Representations, AMS 2003), which are generalizations of comparability graphs. A graph is k-clique-extendible if there is an ordering of the vertices such that whenever two k-sized overlapping cliques A and B have k-1 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 k-C-E 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(mO(k)) time [Hamburger et al. 2017]. When k is 2, such graphs are precisely the well-known class of comparability graphs and when k is 3 they are called triangle-extendible graphs. It has been shown that triangle-extendible 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. 2-C-E graphs) can be recognized in polynomial time, we show that recognizing k-C-E graphs is NP-hard for any fixed k ≥ 3 and co-NP-hard 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 3-colouring problem. We also show that

    • determining whether a given ordering of the vertices of a graph is a k-C-E ordering, and
    • finding an l-sized (or maximum sized) clique in a k-C-E graph, given a k-C-E ordering

    are complete for the parameterized complexity class W[1] when parameterized by k. However we show that the former is fixed-parameter tractable when parameterized by the treewidth of the graph.

  • Pavel Klavík, Dušan Knop and Peter Zeman. 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 NP-complete: 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 GI-complete for a class of graphs, it usually implies NP-completeness 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 NP-complete for cubic colored graphs with sizes of color classes bounded by 8.

  • Stefan Felsner, Kolja Knauer and Torsten Ueckerdt. 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 axis-aligned rectangles in ℝ3. We prove that planar 3-colorable graphs are touching graphs of axis-aligned rectangles in ℝ3, the result implies a characterization of corner polytopes previously obtained by Eppstein and Mumford. A by-product 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 axis-aligned 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.

  • Sriram Bhyravarapu and Subrahmanyam Kalyanasundaram. Combinatorial Bounds for Conflict-free Coloring on Open Neighborhoods

    Abstract: In an undirected graph G, a conflict-free 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 NP-complete. 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.