-
H-Clique-Width and a Hereditary Analogue of Product Structure
Authors:
Petr Hliněný,
Jan Jedelský
Abstract:
We introduce a novel generalization of the notion of clique-width which aims to bridge the gap between classical hereditary width measures and the recently introduced graph product structure theory. Bounding the new H-clique-width, in the special case of H being the class of paths, is equivalent to admitting a hereditary (i.e., induced) product structure of a path times a graph of bounded clique-w…
▽ More
We introduce a novel generalization of the notion of clique-width which aims to bridge the gap between classical hereditary width measures and the recently introduced graph product structure theory. Bounding the new H-clique-width, in the special case of H being the class of paths, is equivalent to admitting a hereditary (i.e., induced) product structure of a path times a graph of bounded clique-width. Furthermore, every graph admitting the usual (non-induced) product structure of a path times a graph of bounded tree-width, has bounded H-clique-width and, as a consequence, it admits the usual product structure in an induced way. We prove further basic properties of H-clique-width in general.
△ Less
Submitted 28 June, 2024; v1 submitted 25 March, 2024;
originally announced March 2024.
-
Note on Min-k-Planar Drawings of Graphs
Authors:
Petr Hliněný,
Lili Ködmön
Abstract:
The k-planar graphs, which are (usually with small values of k such as 1, 2, 3) subject to recent intense research, admit a drawing in which edges are allowed to cross, but each one edge is allowed to carry at most k crossings. In recently introduced [Binucci et al., GD 2023] min-k-planar drawings of graphs, edges may possibly carry more than k crossings, but in any two crossing edges, at least on…
▽ More
The k-planar graphs, which are (usually with small values of k such as 1, 2, 3) subject to recent intense research, admit a drawing in which edges are allowed to cross, but each one edge is allowed to carry at most k crossings. In recently introduced [Binucci et al., GD 2023] min-k-planar drawings of graphs, edges may possibly carry more than k crossings, but in any two crossing edges, at least one of the two must have at most k crossings. In both concepts, one may consider general drawings or a popular restricted concept of drawings called simple. In a simple drawing, every two edges are allowed to cross at most once, and any two edges which share a vertex are forbidden to cross. While, regarding the former concept, it is for k<=3 known (but perhaps not widely known) that every general k-planar graph admits a simple k-planar drawing and this ceases to be true for any k>=4, the difference between general and simple drawings in the latter concept is more striking. We prove that there exist graphs with a min-2-planar drawing, or with a min-3-planar drawing avoiding crossings of adjacent edges, which have no simple min-k-planar drawings for arbitrarily large fixed k.
△ Less
Submitted 6 June, 2024; v1 submitted 21 January, 2024;
originally announced January 2024.
-
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Authors:
Benjamin Bergougnoux,
Jakub Gajarský,
Grzegorz Guśpiel,
Petr Hliněný,
Filip Pokrývka,
Marek Sokołowski
Abstract:
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. Having such a…
▽ More
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. Having such a sequence at hand allows to solve many otherwise hard problems efficiently. Our paper focuses on a comparison of twin-width to the more traditional tree-width on sparse graphs. Namely, we prove that if a graph $G$ of twin-width at most $2$ contains no $K_{t,t}$ subgraph for some integer $t$, then the tree-width of $G$ is bounded by a polynomial function of $t$. As a consequence, for any sparse graph class $\mathcal{C}$ we obtain a polynomial time algorithm which for any input graph $G \in \mathcal{C}$ either outputs a contraction sequence of width at most $c$ (where $c$ depends only on $\mathcal{C}$), or correctly outputs that $G$ has twin-width more than $2$. On the other hand, we present an easy example of a graph class of twin-width $3$ with unbounded tree-width, showing that our result cannot be extended to higher values of twin-width.
△ Less
Submitted 4 July, 2023;
originally announced July 2023.
-
Minimizing an Uncrossed Collection of Drawings
Authors:
Petr Hliněný,
Tomáš Masařík
Abstract:
In this paper, we introduce the following new concept in graph drawing. Our task is to find a small collection of drawings such that they all together satisfy some property that is useful for graph visualization. We propose investigating a property where each edge is not crossed in at least one drawing in the collection. We call such collection uncrossed. Such property is motivated by a quintessen…
▽ More
In this paper, we introduce the following new concept in graph drawing. Our task is to find a small collection of drawings such that they all together satisfy some property that is useful for graph visualization. We propose investigating a property where each edge is not crossed in at least one drawing in the collection. We call such collection uncrossed. Such property is motivated by a quintessential problem of the crossing number, where one asks for a plane drawing where the number of edge crossings is minimum. Indeed, if we are allowed to visualize only one drawing, then the one which minimizes the number of crossings is probably the neatest for the first orientation. However, a collection of drawings where each highlights a different aspect of a graph without any crossings could shed even more light on the graph's structure.
We propose two definitions. First, the uncrossed number, minimizes the number of graph drawings in a collection, satisfying the uncrossed property. Second, the uncrossed crossing number, minimizes the total number of crossings in the collection that satisfy the uncrossed property. For both definitions, we establish initial results. We prove that the uncrossed crossing number is NP-hard, but there is an FPT algorithm parameterized by the solution size.
△ Less
Submitted 31 August, 2023; v1 submitted 15 June, 2023;
originally announced June 2023.
-
Stack and Queue Numbers of Graphs Revisited
Authors:
Petr Hliněný,
Adam Straka
Abstract:
A long-standing question of the mutual relation between the stack and queue numbers of a graph, explicitly emphasized by Dujmović and Wood in 2005, was "half-answered" by Dujmović, Eppstein, Hickingbotham, Morin and Wood in 2022; they proved the existence of a graph family with the queue number at most 4 but unbounded stack number. We give an alternative very short, and still elementary, proof of…
▽ More
A long-standing question of the mutual relation between the stack and queue numbers of a graph, explicitly emphasized by Dujmović and Wood in 2005, was "half-answered" by Dujmović, Eppstein, Hickingbotham, Morin and Wood in 2022; they proved the existence of a graph family with the queue number at most 4 but unbounded stack number. We give an alternative very short, and still elementary, proof of the same fact.
△ Less
Submitted 18 May, 2023; v1 submitted 17 March, 2023;
originally announced March 2023.
-
Twin-width of Planar Graphs; a Short Proof
Authors:
Petr Hliněný
Abstract:
The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from the final resolution; there is a lower bound of 7 coming from a construction by Král' and Lamaison [arXiv, September 2022], and an upper bound of 8 by Hliněný and Jedelský [arXiv, October 2022]. The upper bound (currently best) of 8, however, is rather complicated and involved. In the paper we giv…
▽ More
The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from the final resolution; there is a lower bound of 7 coming from a construction by Král' and Lamaison [arXiv, September 2022], and an upper bound of 8 by Hliněný and Jedelský [arXiv, October 2022]. The upper bound (currently best) of 8, however, is rather complicated and involved. In the paper we give a short and simple self-contained proof that the twin-width of planar graphs is at most 11. We believe that this short proof can also shed more light on the topic of upper bound(s) on the twin-width of planar and beyond-planar graphs in general.
△ Less
Submitted 2 July, 2024; v1 submitted 17 February, 2023;
originally announced February 2023.
-
Twin-width of Planar Graphs is at most 8, and some Related Bounds
Authors:
Petr Hliněný,
Jan Jedelský
Abstract:
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020], and has interesting applications in the areas of logic on graphs and in parameterized algorithmics. Very briefly, the essence of twin-width is in a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of th…
▽ More
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020], and has interesting applications in the areas of logic on graphs and in parameterized algorithmics. Very briefly, the essence of twin-width is in a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. While for many natural graph classes it is known that their twin-width is bounded, published upper bounds on the twin-width in non-trivial cases are very often "astronomically large".
We focus on planar graphs, which are known to have bounded twin-width already since the introduction of it, but it took some time for the first explicit "non-astronomical" upper bounds to come. Namely, in the order of preprint appearance, it was the bound of at most 183 by Jacob and Pilipczuk [arXiv, January 2022], and 583 by Bonnet, Kwon and Wood [arXiv, February 2022]. Subsequent arXiv manuscripts in 2022 improved the bound down to 37 (Bekos et al.), 11 and 9 (both by Hliněný). We further elaborate on the approach used in the latter manuscripts, proving that the twin-width of every planar graph is at most 8, and construct a witnessing contraction sequence in linear time. Note that the currently best lower-bound planar example is of twin-width 7, by Král and Lamaison [arXiv, September 2022]. We also prove small explicit upper bounds on the twin-width of bipartite planar and 1-planar graphs (6 and 16), and of map graphs (38). The common denominator of all these results is the use of a novel specially crafted recursive decomposition of planar graphs, which may be found useful also in other areas.
△ Less
Submitted 7 December, 2023; v1 submitted 16 October, 2022;
originally announced October 2022.
-
Twin-width of Planar Graphs is at most 9, and at most 6 when Bipartite Planar
Authors:
Petr Hliněný
Abstract:
The structural parameter twin-width was introduced by Bonnet et al. in [FOCS 2020], and already this first paper included an asymptotic argument bounding the twin-width of planar graphs by a non-explicit constant. Quite recently, we have seen first small explicit upper bounds of 183 by Jacob and Pilipczuk [arXiv, January 2022], 583 by Bonnet et al. [arXiv, February 2022], and of 37 by Bekos et al.…
▽ More
The structural parameter twin-width was introduced by Bonnet et al. in [FOCS 2020], and already this first paper included an asymptotic argument bounding the twin-width of planar graphs by a non-explicit constant. Quite recently, we have seen first small explicit upper bounds of 183 by Jacob and Pilipczuk [arXiv, January 2022], 583 by Bonnet et al. [arXiv, February 2022], and of 37 by Bekos et al. [arXiv, April 2022]. We prove that the twin-width of planar graphs is at most 9. Furthermore, if a planar graph is also bipartite, then its twin-width is at most 6.
△ Less
Submitted 29 August, 2022; v1 submitted 11 May, 2022;
originally announced May 2022.
-
Graph Product Structure for h-Framed Graphs
Authors:
Michael A. Bekos,
Giordano Da Lozzo,
Petr Hliněný,
Michael Kaufmann
Abstract:
Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as…
▽ More
Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020].
In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size $3\lfloor h/2 \rfloor +\lfloor h/3 \rfloor -1$. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 495 to 81 and from 32225k(k-3) to 61k, respectively. We also employ the product structure machinery to improve the current upper bounds of twin-width of planar and 1-planar graphs from 183 to 37, and from O(1) to 80, respectively. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.
△ Less
Submitted 25 April, 2022;
originally announced April 2022.
-
Automorphisms of Set Families and of Families of Cliques in an Interval Graph in FPT Time
Authors:
Deniz Ağaoğlu Çağırıcı,
Petr Hliněný
Abstract:
We consider the following problem closely related to graph isomorphism. In a simplified version, the task is to compute the automorphism group of a given set family (or a hypergraph), that is, the group of all automorphisms of the given sets which are compatible with some permutation of their elements. In a general setting, the set family in question is a collection of cliques (called marked cliqu…
▽ More
We consider the following problem closely related to graph isomorphism. In a simplified version, the task is to compute the automorphism group of a given set family (or a hypergraph), that is, the group of all automorphisms of the given sets which are compatible with some permutation of their elements. In a general setting, the set family in question is a collection of cliques (called marked cliques) of a given interval graph, and the task is to compute the group of all permutations of the cliques which result from some automorpism of the underlying interval graph. This problem is obviously at least as hard as the graph isomorphism (GI-hard) already in the simplified version -- consider the set family of edges of a graph, and we give an FPT-time algorithm parameterized by the maximum number of sets in the family which are incomparable by inclusion (its antichain size). To our best knowledge, the general version of the problem has not been formulated in the literature so far. The problem has been inspired by the research of special cases of the isomorphism problem of chordal graphs; namely, the simplified set-family version is the core of our FPT algorithm for the isomorphism of so-called Sd-graphs [MFCS 2021], and the general version extends and improves a cumbersome technical step in our FPT algorithm for the isomorphism of chordal graphs of bounded leafage [WALCOM 2022]. The new algorithm combines two classical tools -- PQ-trees of interval graphs and Babai's tower-of-groups, in a nontrivial way.
△ Less
Submitted 28 June, 2022; v1 submitted 25 February, 2022;
originally announced February 2022.
-
Twin-width and Transductions of Proper k-Mixed-Thin Graphs
Authors:
Jakub Balabán,
Petr Hliněný,
Jan Jedelský
Abstract:
The new graph parameter twin-width, introduced by Bonnet, Kim, Thomass e and Watrigant in 2020, allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, classes of efficiently bounded twin-width include proper interval graphs, and (as digraphs) posets of width k. Inspired…
▽ More
The new graph parameter twin-width, introduced by Bonnet, Kim, Thomass e and Watrigant in 2020, allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, classes of efficiently bounded twin-width include proper interval graphs, and (as digraphs) posets of width k. Inspired by an existing generalization of interval graphs into so-called k-thin graphs, we define a new class of proper k-mixed-thin graphs which largely generalizes proper interval graphs. We prove that proper k-mixed-thin graphs have twin-width linear in k, and that a slight subclass of k-mixed-thin graphs is transduction-equivalent to posets of width k' such that there is a quadratic-polynomial relation between k and k'. In addition to that, we also give an abstract overview of the so-called red potential method which we use to prove our twin-width bounds.
△ Less
Submitted 6 November, 2022; v1 submitted 25 February, 2022;
originally announced February 2022.
-
Twin-Width is Linear in the Poset Width
Authors:
Jakub Balabán,
Petr Hliněný
Abstract:
Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced just very recently, in 2020 by Bonnet, Kim, Thomasse and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT.…
▽ More
Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced just very recently, in 2020 by Bonnet, Kim, Thomasse and Watrigant. One of the core results of these authors is that FO model checking on graph classes of bounded twin-width is in FPT. With that result, they also claimed that posets of bounded width have bounded twin-width, thus capturing prior result on FO model checking of posets of bounded width in FPT. However, their translation from poset width to twin-width was indirect and giving only a very loose double-exponential bound. We prove that posets of width d have twin-width at most 9d with a direct and elegant argument, and show that this bound is asymptotically tight. Specially, for posets of width 2 we prove that in the worst case their twin-width is also equal 2. These two theoretical results are complemented with straightforward algorithms to construct the respective contraction sequence for a given poset.
△ Less
Submitted 8 July, 2021; v1 submitted 29 June, 2021;
originally announced June 2021.
-
On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
Authors:
Petr Hliněný,
Michal Korbela
Abstract:
A recent result of Bokal et al. [Combinatorica, 2022] proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is c=13. The key to that result is an inductive construction of a family of 13-crossing-critical graphs with many vertices of arbitrarily high degrees. While the inductive part of the construction is rather easy, it all relies on the…
▽ More
A recent result of Bokal et al. [Combinatorica, 2022] proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is c=13. The key to that result is an inductive construction of a family of 13-crossing-critical graphs with many vertices of arbitrarily high degrees. While the inductive part of the construction is rather easy, it all relies on the fact that a certain 17-vertex base graph has the crossing number 13, which was originally verified only by a machine-readable computer proof. We provide a relatively short self-contained computer-free proof of the latter fact. Furthermore, we subsequently generalize the critical construction in order to provide a definitive answer to a remaining open question of this research area; we prove that for every c>=13 and integers d,q, there exists a c-crossing-critical graph with more than q vertices of each of the degrees 3,4,...,d.
△ Less
Submitted 1 March, 2024; v1 submitted 3 May, 2021;
originally announced May 2021.
-
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
Authors:
Jan Bok,
Jiří Fiala,
Petr Hliněný,
Nikola Jedličková,
Jan Kratochvíl
Abstract:
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {\em graphs with semi-edges}. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symm…
▽ More
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {\em graphs with semi-edges}. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symmetric graphs, and in computer science in the theory of local computations. In 1991, Abello et al. asked for a classification of the computational complexity of deciding if an input graph covers a fixed target graph, in the ordinary setting (of graphs with only edges). Although many general results are known, the full classification is still open. In spite of that, we propose to study the more general case of covering graphs composed of normal edges (including multiedges and loops) and so-called semi-edges. Semi-edges are becoming increasingly popular in modern topological graph theory, as well as in mathematical physics. They also naturally occur in the local computation setting, since they are lifted to matchings in the covering graph. We show that the presence of semi-edges makes the covering problem considerably harder; e.g., it is no longer sufficient to specify the vertex mapping induced by the covering, but one necessarily has to deal with the edge mapping as well. We show some solvable cases, and completely characterize the complexity of the already very nontrivial problem of covering one- and two-vertex (multi)graphs with semi-edges. Our NP-hardness results are proven for simple input graphs, and in the case of regular two-vertex target graphs, even for bipartite ones. This provides a strengthening of previously known results for covering graphs without semi-edges, and may contribute to better understanding of this notion and its complexity.
△ Less
Submitted 28 March, 2021;
originally announced March 2021.
-
Exact Crossing Number Parameterized by Vertex Cover
Authors:
Petr Hliněný,
Abhisekh Sankaran
Abstract:
We prove that the exact crossing number of a graph can be efficiently computed for simple graphs having bounded vertex cover. In more precise words, Crossing Number is in FPT when parameterized by the vertex cover size. This is a notable advance since we know only very few nontrivial examples of graph classes with unbounded and yet efficiently computable crossing number. Our result can be viewed a…
▽ More
We prove that the exact crossing number of a graph can be efficiently computed for simple graphs having bounded vertex cover. In more precise words, Crossing Number is in FPT when parameterized by the vertex cover size. This is a notable advance since we know only very few nontrivial examples of graph classes with unbounded and yet efficiently computable crossing number. Our result can be viewed as a strengthening of a previous result of Lokshtanov [arXiv, 2015] that Optimal Linear Arrangement is in FPT when parameterized by the vertex cover size, and we use a similar approach of reducing the problem to a tractable instance of Integer Quadratic Programming as in Lokshtanov's paper.
△ Less
Submitted 5 September, 2019; v1 submitted 14 June, 2019;
originally announced June 2019.
-
On Colourability of Polygon Visibility Graphs
Authors:
Onur Çağirici,
Petr Hliněný,
Bodhayan Roy
Abstract:
We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and prove that the 5-colourability question is already NP-complete for them. For visibility graphs of polygons with holes, we prove that the 4-colourability question is NP-complete.
We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and prove that the 5-colourability question is already NP-complete for them. For visibility graphs of polygons with holes, we prove that the 4-colourability question is NP-complete.
△ Less
Submitted 5 June, 2019;
originally announced June 2019.
-
A New Perspective on FO Model Checking of Dense Graph Classes
Authors:
Jakub Gajarský,
Petr Hliněný,
Daniel Lokshtanov,
Jan Obdržálek,
M. S. Ramanujan
Abstract:
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes which are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequ…
▽ More
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes which are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking of any graph class which is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.
△ Less
Submitted 4 May, 2018;
originally announced May 2018.
-
On Degree Properties of Crossing-Critical Families of Graphs
Authors:
Drago Bokal,
Mojca Bračič,
Marek Derňár,
Petr Hliněný
Abstract:
Answering an open question from 2007, we construct infinite $k$-crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large~$k$. To answer this question, we introduce several properties of infinite families of graphs and operations on the families allowing us to obtain new families preserving those properties. This conceptual setup allows us…
▽ More
Answering an open question from 2007, we construct infinite $k$-crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large~$k$. To answer this question, we introduce several properties of infinite families of graphs and operations on the families allowing us to obtain new families preserving those properties. This conceptual setup allows us to answer general questions on behaviour of degrees in crossing-critical graphs: we show that, for any set of integers $D$ such that $\min(D)\geq 3$ and $3,4\in D$, and for any sufficiently large $k$, there exists a $k$-crossing-critical family such that the numbers in $D$ are precisely the vertex degrees that occur arbitrarily often in (large enough) graphs of this family. Furthermore, even if both $D$ and some average degree in the interval $(3,6)$ are prescribed, $k$-crossing-critical families exist for any sufficiently large $k$.
△ Less
Submitted 15 March, 2019; v1 submitted 28 March, 2018;
originally announced March 2018.
-
Structure and generation of crossing-critical graphs
Authors:
Zdeněk Dvořák,
Petr Hliněný,
Bojan Mohar
Abstract:
We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_3,3, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded…
▽ More
We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_3,3, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.
△ Less
Submitted 5 March, 2018;
originally announced March 2018.
-
Shrub-depth: Capturing Height of Dense Graphs
Authors:
Robert Ganian,
Petr Hliněný,
Jaroslav Nešetřil,
Jan Obdržálek,
Patrice Ossona de Mendez
Abstract:
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to t…
▽ More
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower $ω$ levels of the MSO1 transduction hierarchy of simple graphs.
△ Less
Submitted 30 January, 2019; v1 submitted 2 July, 2017;
originally announced July 2017.
-
Parameterized Shifted Combinatorial Optimization
Authors:
Jakub Gajarský,
Petr Hliněný,
Martin Koutecký,
Shmuel Onn
Abstract:
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimiza…
▽ More
Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, which is typically much harder. Already with explicitly given input set the shifted problem may be NP-hard. In this article we initiate a study of the parameterized complexity of this framework. First we show that shifting over an explicitly given set with its cardinality as the parameter may be in XP, FPT or P, depending on the objective function. Second, we study the shifted problem over sets definable in MSO logic (which includes, e.g., the well known MSO partitioning problems). Our main results here are that shifted combinatorial optimization over MSO definable sets is in XP with respect to the MSO formula and the treewidth (or more generally clique-width) of the input graph, and is W[1]-hard even under further severe restrictions.
△ Less
Submitted 22 February, 2017;
originally announced February 2017.
-
A Short Proof of Euler--Poincaré Formula
Authors:
Petr Hliněný
Abstract:
"V - E + F = 2", the famous Euler's polyhedral formula, has a natural generalization to convex polytopes in every finite dimension, also known as the Euler-Poincaré Formula. We provide another short inductive proof of the general formula. Our proof is self-contained and it does not use shellability of polytopes.
"V - E + F = 2", the famous Euler's polyhedral formula, has a natural generalization to convex polytopes in every finite dimension, also known as the Euler-Poincaré Formula. We provide another short inductive proof of the general formula. Our proof is self-contained and it does not use shellability of polytopes.
△ Less
Submitted 9 September, 2021; v1 submitted 5 December, 2016;
originally announced December 2016.
-
A Simpler Self-reduction Algorithm for Matroid Path-width
Authors:
Petr Hliněný
Abstract:
Path-width of matroids naturally generalizes the better known parameter of path-width for graphs, and is NP-hard by a reduction from the graph case. While the term matroid path-width was formally introduced by Geelen-Gerards-Whittle [JCTB 2006] in pure matroid theory, it was soon recognized by Kashyap [SIDMA 2008] that it is the same concept as long-studied so called trellis complexity in coding t…
▽ More
Path-width of matroids naturally generalizes the better known parameter of path-width for graphs, and is NP-hard by a reduction from the graph case. While the term matroid path-width was formally introduced by Geelen-Gerards-Whittle [JCTB 2006] in pure matroid theory, it was soon recognized by Kashyap [SIDMA 2008] that it is the same concept as long-studied so called trellis complexity in coding theory, later named trellis-width, and hence it is an interesting notion also from the algorithmic perspective. It follows from a result of Hlineny [JCTB 2006] that the decision problem, whether a given matroid over a finite field has path-width at most t, is fixed-parameter tractable (FPT) in t, but this result does not give any clue about constructing a path-decomposition. The first constructive and rather complicated FPT algorithm for path-width of matroids over a finite field was given by Jeong-Kim-Oum [SODA 2016]. Here we propose a simpler "self-reduction" FPT algorithm for a path-decomposition. Precisely, we design an efficient routine that constructs an optimal path-decomposition of a matroid by calling any subroutine for testing whether the path-width of a matroid is at most t (such as the aforementioned decision algorithm for matroid path-width).
△ Less
Submitted 18 April, 2018; v1 submitted 31 May, 2016;
originally announced May 2016.
-
Crossing Number is Hard for Kernelization
Authors:
Petr Hliněný,
Marek Derňár
Abstract:
The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed- parameter tractable for the parameter k [Grohe]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time…
▽ More
The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed- parameter tractable for the parameter k [Grohe]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge.
△ Less
Submitted 18 February, 2016; v1 submitted 8 December, 2015;
originally announced December 2015.
-
On Hardness of the Joint Crossing Number
Authors:
Petr Hliněný,
Gelasio Salazar
Abstract:
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly consi…
▽ More
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar.
△ Less
Submitted 6 September, 2015;
originally announced September 2015.
-
First order limits of sparse graphs: Plane trees and path-width
Authors:
Jakub Gajarsky,
Petr Hlineny,
Tomas Kaiser,
Daniel Kral,
Martin Kupec,
Jan Obdrzalek,
Sebastian Ordyniak,
Vojtech Tuma
Abstract:
Nesetril and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs…
▽ More
Nesetril and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree-depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path-width has a limit modeling.
△ Less
Submitted 31 March, 2016; v1 submitted 30 April, 2015;
originally announced April 2015.
-
Tree-depth and Vertex-minors
Authors:
Petr Hliněný,
O-joung Kwon,
Jan Obdržálek,
Sebastian Ordyniak
Abstract:
In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for "depth" parameters of graphs, namely for the tree-depth and related new shrub-depth. We show that shrub-depth is monotone under taking vertex-minors, and that every graph class of…
▽ More
In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for "depth" parameters of graphs, namely for the tree-depth and related new shrub-depth. We show that shrub-depth is monotone under taking vertex-minors, and that every graph class of bounded shrub-depth can be obtained via vertex-minors of graphs of bounded tree-depth. We also consider the same questions for bipartite graphs and pivot-minors.
△ Less
Submitted 27 March, 2014;
originally announced March 2014.
-
Toroidal grid minors and stretch in embedded graphs
Authors:
Markus Chimani,
Petr Hlineny,
Gelasio Salazar
Abstract:
We investigate the toroidal expanse of an embedded graph G, that is, the size of the largest toroidal grid contained in G as a minor. In the course of this work we introduce a new embedding density parameter, the stretch of an embedded graph G, and use it to bound the toroidal expanse from above and from below within a constant factor depending only on the genus and the maximum degree. We also sho…
▽ More
We investigate the toroidal expanse of an embedded graph G, that is, the size of the largest toroidal grid contained in G as a minor. In the course of this work we introduce a new embedding density parameter, the stretch of an embedded graph G, and use it to bound the toroidal expanse from above and from below within a constant factor depending only on the genus and the maximum degree. We also show that these parameters are tightly related to the planar crossing number of G. As a consequence of our bounds, we derive an efficient constant factor approximation algorithm for the toroidal expanse and for the crossing number of a surface-embedded graph with bounded maximum degree.
△ Less
Submitted 5 June, 2019; v1 submitted 5 March, 2014;
originally announced March 2014.
