Inserting a vertex into a planar graph

ABSTRACT

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 E_v = {(v, u) | u ∈ V}, in which all crossings involve E_v. 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.

REFERENCES

• 1: Drago Bokal , Gasper Fijavz , Bojan Mohar, The Minor Crossing Number, SIAM Journal on Discrete Mathematics, v.20 n.2, p.344-356, 2006 [doi>10.1137/05062706X]
• 2: C. Buchheim, M. Chimani, D. Ebner, C. Gutwenger, M. Jünger, G. W. Klau, P. Mutzel, and R. Weiskircher. A branch-and-cut approach to the crossing number problem. Discrete Optimization, 5(2):373--388, 2008.
• 3: M. Chimani and C. Gutwenger. Algorithms for the hypergraph and the minor crossing number problems. In Proc. ISAAC '07, volume 4835 of LNCS, pages 184--195. Springer, 2007.
• 4: Sergio Cabello , Bojan Mohar, Crossing and Weighted Crossing Number of Near-Planar Graphs, Graph Drawing: 16th International Symposium, GD 2008, Heraklion, Crete, Greece, September 21-24, 2008. Revised Papers, Springer-Verlag, Berlin, Heidelberg, 2009 [doi>10.1007/978-3-642-00219-9_5]
• 5: M. Chimani, C. Gutwenger, and P. Mutzel. Experiments on exact crossing minimization using column generation. In Proc. WEA '06, volume 4007 of LNCS, pages 303--315. Springer, 2006.
• 6: M. Chimani, P. Hliněný, and P. Mutzel. Vertex Insertion approximates the Crossing Number for Apex Graphs. submitted. A preliminary version titled Approximating the Crossing Number of Apex Graphs appeared as a poster at Graph Drawing '08.
• 7: Markus Chimani , Petra Mutzel , Immanuel Bomze, A New Approach to Exact Crossing Minimization, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_24]
• 8: Giuseppe Di Battista , Roberto Tamassia, On-Line Planarity Testing, SIAM Journal on Computing, v.25 n.5, p.956-997, Oct. 1996 [doi>10.1137/S0097539794280736]
• 9: Keith Edwards , Graham Farr, An Algorithm for Finding Large Induced Planar Subgraphs, Revised Papers from the 9th International Symposium on Graph Drawing, p.75-83, September 23-26, 2001
• 10: Guy Even , Sudipto Guha , Baruch Schieber, Improved approximations of crossings in graph drawings, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.296-305, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335340]
• 11: M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4(3):312--316, 1983.
• 12: I. Gitler, P. Hliněný, J. Leanos, and G. Salazar. The crossing number of a projective graph is quadratic in the face-width. Electronic Notes in Discrete Mathematics, 29:219--223, 2007.
• 13: Martin Grohe, Computing crossing numbers in quadratic time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.231-236, July 2001, Hersonissos, Greece [doi>10.1145/380752.380805]
• 14: Carsten Gutwenger , Petra Mutzel, A Linear Time Implementation of SPQR-Trees, Proceedings of the 8th International Symposium on Graph Drawing, p.77-90, September 20-23, 2000
• 15: C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. Algorithmica, 41:289--308, 2005.
• 16: Petr Hliněný, Crossing number is hard for cubic graphs, Journal of Combinatorial Theory Series B, v.96 n.4, p.455-471, July 2006 [doi>10.1016/j.jctb.2005.09.009]
• 17: P. Hliněný and G. Salazar. On the crossing number of almost planar graphs. In Proc. Graph Drawing '06, volume 4372 of LNCS, pages 162--173. Springer, 2007.
• 18: J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(3):135--158, 1973.
• 19: Ken-ichi Kawarabayashi , Buce Reed, Computing crossing number in linear time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250848]
• 20: I. Vrt'o. Crossing numbers of graphs: A bibliography. See ftp://ftp.ifi.savba.sk/pub/imrich/crobib.pdf, 2008.
• 21: C. Wolf. Inserting a vertex into a planar graph. Master's thesis, Dortmund University of Technology, 2008. See http://ls11-www.cs.unidortmund.de/people/gutweng/diploma_thesis_wolf.pdf.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory