Document Open Access Logo

Inserting Multiple Edges into a Planar Graph

Authors Markus Chimani, Petr Hlinený

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.30.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Markus Chimani
Petr Hlinený

Cite As Get BibTex

Markus Chimani and Petr Hlinený. Inserting Multiple Edges into a Planar Graph. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.30

Abstract

Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not 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. An optimal solution to this problem is known to approximate the crossing number of the graph G+F. 

Finding an exact solution to MEI is NP-hard for general F, but linear time solvable for the special case of |F|=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [Chimani-Hlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees. We give the first exact algorithm for this problem; it requires only O(|V(G)|) time for any constant k.

Subject Classification

Keywords
  • crossing number
  • edge insertion
  • parameterized complexity
  • path homotopy
  • funnel algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity relationship diagrams. Journal of Systems and Software, 4:163-173, 1984. Google Scholar
  2. S. N. Bhatt and F. T. Leighton. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci., 28(2):300-343, 1984. Google Scholar
  3. D. Bienstock and C. L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica, 5(1):93-109, 1990. Google Scholar
  4. S. Cabello. Hardness of approximation for crossing number. Discrete & Computational Geometry, 49(2):348-358, 2013. Google Scholar
  5. S. Cabello and B. Mohar. Crossing number and weighted crossing number of near-planar graphs. Algorithmica, 60(3):484-504, 2011. Google Scholar
  6. S. Cabello and B. Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput., 42(5):1803-1829, 2013. Google Scholar
  7. B. Chazelle. A theorem on polygon cutting with applications. In Proc. FOCS'82, pages 339-349. IEEE Computer Society, 1982. Google Scholar
  8. M. Chimani. Computing Crossing Numbers. PhD thesis, TU Dortmund, Germany, 2008. URL: http://hdl.handle.net/2003/25955.
  9. M. Chimani and C. Gutwenger. Advances in the planarization method: effective multiple edge insertions. J. Graph Algorithms Appl., 16(3):729-757, 2012. Google Scholar
  10. M. Chimani, C. Gutwenger, P. Mutzel, and C. Wolf. Inserting a vertex into a planar graph. In Proc. SODA'09, pages 375-383, 2009. Google Scholar
  11. M. Chimani and P. Hliněný. A tighter insertion-based approximation of the crossing number. In Proc. ICALP'11, volume 6755 of LNCS, pages 122-134. Springer, 2011. Google Scholar
  12. M. Chimani, P. Hliněný, and P. Mutzel. Vertex insertion approximates the crossing number for apex graphs. European Journal of Combinatorics, 33:326-335, 2012. Google Scholar
  13. J. Chuzhoy. An algorithm for the graph crossing number problem. In Proc. STOC'11, pages 303-312. ACM, 2011. Google Scholar
  14. J. Chuzhoy, Y. Makarychev, and A. Sidiropoulos. On graph crossing number and edge planarization. In Proc. SODA'11, pages 1050-1069. ACM Press, 2011. Google Scholar
  15. É. Colin de Verdière and A. Schrijver. Shortest vertex-disjoint two-face paths in planar graphs. ACM Transactions on Algorithms, 7(2):19, 2011. Google Scholar
  16. G. Di Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25:956-997, 1996. Google Scholar
  17. G. Even, S. Guha, and B. Schieber. Improved approximations of crossings in graph drawings and VLSI layout areas. SIAM J. Comput., 32(1):231-252, 2002. Google Scholar
  18. M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Alg. Discr. Meth., 4:312-316, 1983. Google Scholar
  19. I. Gitler, P. Hliněný, J. Leanos, and G. Salazar. The crossing number of a projective graph is quadratic in the face-width. Electronic Journal of Combinatorics, 15(1):#R46, 2008. Google Scholar
  20. M. Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci., 68(2):285-302, 2004. Google Scholar
  21. C. Gutwenger and P. Mutzel. A linear time implementation of SPQR trees. In Proc. GD'00, volume 1984 of LNCS, pages 77-90. Springer, 2001. Google Scholar
  22. C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. Algorithmica, 41(4):289-308, 2005. Google Scholar
  23. J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Comput. Geom., 4:63-97, 1994. Google Scholar
  24. P. Hliněný and M. Chimani. Approximating the crossing number of graphs embeddable in any orientable surface. In Proc. SODA'10, pages 918-927, 2010. Google Scholar
  25. P. Hliněný and G. Salazar. On the crossing number of almost planar graphs. In Proc. GD'05, volume 4372 of LNCS, pages 162-173. Springer, 2006. Google Scholar
  26. P. Hliněný and G. Salazar. Approximating the crossing number of toroidal graphs. In Proc. ISAAC'07, volume 4835 of LNCS, pages 148-159. Springer, 2007. Google Scholar
  27. J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(3):135-158, 1973. Google Scholar
  28. K-I. Kawarabayashi and B. Reed. Computing crossing number in linear time. In Proc. STOC'07, pages 382-390, 2007. Google Scholar
  29. P. Klein, S. Rao, M. Rauch, and S. Subramanian. Faster shortest-path algorithms for planar graphs. In Proc. STOC'94, pages 27-37, 1994. Google Scholar
  30. Y. Kobayashi and C. Sommer. On shortest disjoint paths in planar graphs. Discrete Optimization, 7(4):234-245, 2010. Google Scholar
  31. D.-T. Lee and F. P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393-410, 1984. Google Scholar
  32. M. Schaefer. The graph crossing number and its variants: A survey. Electronic Journal of Combinatorics, #DS21, May 15, 2014. Google Scholar
  33. M. Thorup. Undirected single source shortest paths with positive integer weights in linear time. Journal of the ACM, 46:362-394, 1999. Google Scholar
  34. W. T. Tutte. Connectivity in graphs, volume 15 of Mathematical Expositions. University of Toronto Press, 1966. Google Scholar
  35. T. Ziegler. Crossing Minimization in Automatic Graph Drawing. PhD thesis, Saarland University, Germany, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact