Clustered planarity testing revisited

The Hanani--Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani--Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully generalizes to problems in scheduling, network design and capacited location, its dynamic programming approaches do not. One often relies on strong polyhedral relaxations for corresponding integer programs instead. Among other results, we construct such a relaxation for the time-invariant incremental knapsack problem (IIK), and study classes of valid inequalities for MinKnap. IIK is covered in the first part of this thesis. It is a generalization of the max-knapsack problem to a discrete multi-period setting. At each time, capacity increases and items can be added, but not removed from the knapsack. The goal is to maximize the sum of profits over all times. IIK models scenarios in specific financial markets and governmental decision processes. It is known to be strongly NP-hard and there has been work on approximation algorithms for special cases. We settle the complexity of IIK by designing a PTAS, and provide several extensions of the technique. The second part is on MinKnap and divided into two chapters. One is motivated by a recent work on disjunctive relaxations for MinKnap with fixed objective function, where we reduce the size of the construction. The other focuses on a class of bounded pitch inequalities, that generalize the unweighted cover inequalities for MinKnap. While separating over pitch-1 inequalities is NP-hard, we show that approximate separation over the set of pitch-1 and pitch-2 inequalities can be done in polynomial time. We also investigate integrality gaps of linear relaxations for MinKnap when these inequalities are added. Consequently we show that, for any fixed t, the t-th CG closure of the natural relaxation has unbounded gap. The last chapter deals with questions in clustered planarity testing. The Hanani-Tutte theorem is a classical result that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. We conclude by a short proof, using matroid intersection, for a result by Di Battista and Frati on embedded clustered graphs.

EPFL2019

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossing. Conway's Thrackle Conjecture says that a thrackle cannot have more edges than vertices. By a computational approach we improve the previously known upper bound of 1.5n on the maximal number of edges in a thrackle with n vertices to 1.428n. Moreover, our method yields an algorithm with a finite running time that for any ε > 0 either verifies the upper bound of (1 + ε)n on the maximum number of edges in a thrackle or disproves the conjecture. It is not hard to see that any simple graph admits a poly-line drawing in the plane such that each edge is represented by a polygonal curve with at most three bends, and each edge crossings realizes a prescribed angle α. We show that if we restrict the number of bends per edge to two and allow edges to cross in k different angles, a graph on n vertices admitting such a drawing can have at most O(nk2) edges. This generalizes a previous result of Arikushi et al., in which the authors treated a special case of our problem, where k = 1 and the prescribed angle has 90 degrees. The classical result known as Hanani-Tutte Theorem states that a graph is planar if and only if it admits a drawing in the plane in which each pair of non-adjacent edges crosses an even number of times. We prove the following monotone variant of this result, conjectured by J.Pach and G.Tóth. If G has an x-monotone drawing in which every pair of independent edges crosses evenly, then G has an x-monotone embedding (i.e. a drawing without crossings) with the same vertex locations. We show several interesting algorithmic consequences of this result. In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times. A pair of edges is independent (or non-adjacent) if they share no endpoint. For a graph G we let ocr(G) be the smallest number of odd pairs in a drawing of G and let iocr(G) be the smallest number of independent odd pairs in a drawing of G. We construct a graph G with iocr(G) < ocr(G), answering a question by Székely, and –for the first time– giving evidence that crossings of adjacent edges may not always be trivial to eliminate.

EPFL2012

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

EPFL2019

Intersection Patterns of Edges in Topological Graphs

Radoslav Fulek

EPFL2012