Interaktivní osnova
Supplementary lecture materials II
Solving the planar insertion problems
A variation on crossing number problems....
Definition. Given a planar graph G and a "local structure" S (an edge, vertex, or a set of edges, etc) to be inserted into G, the planar insertion problem of S into G is the problem to find a drawing of G+S minimizing the number of crossing under an additional assumption that the induced subdrawing of G is plane.
- Carsten Gutwenger, Petra Mutzel, René Weiskircher: Inserting an edge into a planar graph. SODA 2001: 246-255.
Computing a crossing minimum drawing of a given planar graph G augmented by an additional edge e where all crossings involve e, has been a long standing open problem in graph drawing. Alternatively, the problem can be stated as finding a combinatorial embedding of a planar graph G where the given edge e can be inserted with the minimum number of crossings. Many problems concerned with the optimization over the set of all combinatorial embeddings of a planar graph turned out to be NP-hard. Surprisingly, we found a conceptually simple linear time algorithm based on SPQR-trees, that is able to find a solution with the minimum number of crossings.
- Markus Chimani, Carsten Gutwenger, Petra Mutzel, Christian Wolf: Inserting a vertex into a planar graph. SODA 2009: 375-383.
We consider the problem of computing a crossing minimum drawing of a given planar graph G = (V, E) augmented by a star, i.e., an additional vertex v together with its incident edges Ev = {(v, u) | u ∈ V}, in which all crossings involve Ev. Alternatively, the problem can be stated as finding a planar embedding of G, in which the given star can be inserted requiring the minimum number of crossings. This is a generalization of the crossing minimum edge insertion problem [15], and can help to find improved approximations for the crossing minimization problem. Indeed, in practice, the algorithm for the crossing minimum edge insertion problem turned out to be the key for obtaining the currently strongest approximate solutions for the crossing number of general graphs. The generalization considered here can lead to even better solutions for the crossing minimization problem. Furthermore, it offers new insight into the crossing number problem for almost-planar and apex graphs.
It has been an open problem whether the star insertion problem is polynomially solvable. We give an affirmative answer by describing the first efficient algorithm for this problem. This algorithm uses the SPQR-tree data structure to handle the exponential number of possible embeddings, in conjunction with dynamic programming schemes for which we introduce partitioning cost subproblems.
Hardness of adding an edge (!!!)
- Sergio Cabello, Bojan Mohar: Adding one edge to planar graphs makes crossing number hard. Symposium on Computational Geometry 2010: 68-76.
A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show that it is NP-hard to compute the crossing number of near-planar graphs. The main idea in the reduction is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This approach can be used to prove hardness of some other geometric problems. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hliněný.
- Besides the extensions mentioned in this paper, the same reduction also shows hardness of exact crossing number for projective almost-planar graphs.
When insertion solution approximates the crossing number
- Petr Hliněný, Gelasio Salazar: On the Crossing Number of Almost Planar Graphs. Graph Drawing 2006: 162-173.
- Sergio Cabello, Bojan Mohar: Crossing and Weighted Crossing Number of Near-Planar Graphs. Graph Drawing 2008: 38-49
A nonplanar graph G is near-planar if it contains an edge e such that G − e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hliněný and Salazar (Graph Drawing GD 2006).
- Markus Chimani, Petr Hliněný, Petra Mutzel: Approximating the Crossing Number of Apex Graphs. Graph Drawing 2008: 432-434.
When insertion solution approximates the crossing number, II
- Markus Chimani, Petr Hliněný. A Tighter Insertion-based Approximation of the Crossing Number. Submitted 2011.
Abstract. Let G be a planar graph and F a set of additional edges not yet in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. As an exact solution to MEI is NP-hard for general F, we present the rst approximation algorithm for MEI which achieves an additive approximation factor (depending only on the size of F and the maximum degree of G). Our algorithm seems to be the rst directly implementable one in that realm, too, next to the single edge insertion.
It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of the F-almost-planar graph G+F, while computing the crossing number of G+F exactly is NP-hard already when |F| = 1. Hence our algorithm induces new, improved approximation bounds for the crossing number problem of F-almost-planar graphs, achieving constant-factor approximation for the large class of such graphs of bounded degrees and bounded size of F.
