Document Open Access Logo

Extending Partial 1-Planar Drawings

Authors Eduard Eiben , Robert Ganian , Thekla Hamm, Fabian Klute , Martin Nöllenburg

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.43.pdf
  • Filesize: 0.83 MB
  • 19 pages

Document Identifiers

Author Details

Eduard Eiben
  • Department of Computer Science, Royal Holloway, University of London, Egham, United Kingdom
Robert Ganian
  • Algorithms and Complexity Group, TU Wien, Austria
Thekla Hamm
  • Algorithms and Complexity Group, TU Wien, Austria
Fabian Klute
  • Algorithms and Complexity Group, TU Wien, Austria
Martin Nöllenburg
  • Algorithms and Complexity Group, TU Wien, Austria

Funding

  • Ganian, Robert: Robert Ganian acknowledges support by the Austrian Science Fund (FWF, project P31336).
  • Hamm, Thekla: Thekla Hamm acknowledges support by the Austrian Science Fund (FWF, projects P31336 and W1255-N23).

Cite AsGet BibTex

Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, and Martin Nöllenburg. Extending Partial 1-Planar Drawings. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.43

Abstract

Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing. In such an extension problem, we are given a tuple (G,H,ℋ) consisting of a graph G, a connected subgraph H of G and a drawing ℋ of H, and the task is to extend ℋ into a drawing of G while maintaining some desired property of the drawing, such as planarity. In this paper we study the problem of extending partial 1-planar drawings, which are drawings in the plane that allow each edge to have at most one crossing. In addition we consider the subclass of IC-planar drawings, which are 1-planar drawings with independent crossings. Recognizing 1-planar graphs as well as IC-planar graphs is NP-complete and the NP-completeness easily carries over to the extension problem. Therefore, our focus lies on establishing the tractability of such extension problems in a weaker sense than polynomial-time tractability. Here, we show that both problems are fixed-parameter tractable when parameterized by the number of edges missing from H, i.e., the edge deletion distance between H and G. The second part of the paper then turns to a more powerful parameterization which is based on measuring the vertex+edge deletion distance between the partial and complete drawing, i.e., the minimum number of vertices and edges that need to be deleted to obtain H from G.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Computational geometry
Keywords
  • Extension problems
  • 1-planarity
  • parameterized algorithms

Metrics

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

Related Versions

References

  1. Michael Albertson. Chromatic number, independence ratio, and crossing number. ARS MATHEMATICA CONTEMPORANEA, 1(1):1-6, 2008. URL: https://doi.org/10.26493/1855-3974.10.2d0.
  2. Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, and Ignaz Rutter. Testing planarity of partially embedded graphs. ACM Trans. Algorithms, 11(4):32:1-32:42, 2015. URL: https://doi.org/10.1145/2629341.
  3. Alan Arroyo, Martin Derka, and Irene Parada. Extending simple drawings. In Daniel Archambault and Csaba D. Tóth, editors, 27th International Symposium on Graph Drawing and Network Visualization (GD'19), volume 11904 of LNCS, pages 230-243. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-35802-0_18.
  4. Alan Arroyo, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber, and Tilo Wiedera. Extending simple drawings with one edge is hard. CoRR, abs/1909.07347, 2019. Accepted for presentation at WG'20. URL: http://arxiv.org/abs/1909.07347.
  5. Franz J. Brandenburg. Recognizing IC-planar and NIC-planar graphs. J. Graph Algorithms Appl., 22(2):239-271, 2018. URL: https://doi.org/10.7155/jgaa.00466.
  6. Franz J. Brandenburg, Walter Didimo, William S. Evans, Philipp Kindermann, Giuseppe Liotta, and Fabrizio Montecchiani. Recognizing and drawing IC-planar graphs. Theor. Comput. Sci., 636:1-16, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.026.
  7. Guido Brückner and Ignaz Rutter. Partial and constrained level planarity. In Philip N. Klein, editor, Discrete Algorithms (SODA'17), pages 2000-2011. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.130.
  8. Sergio Cabello and Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput., 42(5):1803-1829, 2013. URL: https://doi.org/10.1137/120872310.
  9. Erin W. Chambers, David Eppstein, Michael T. Goodrich, and Maarten Löffler. Drawing graphs in the plane with a prescribed outer face and polynomial area. J. Graph Algorithms Appl., 16(2):243-259, 2012. URL: https://doi.org/10.7155/jgaa.00257.
  10. Timothy M. Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel, and Marcus Schaefer. Drawing partially embedded and simultaneously planar graphs. J. Graph Algorithms Appl., 19(2):681-706, 2015. URL: https://doi.org/10.7155/jgaa.00375.
  11. Steven Chaplick, Paul Dorbec, Jan Kratochvíl, Mickaël Montassier, and Juraj Stacho. Contact representations of planar graphs: Extending a partial representation is hard. In Dieter Kratsch and Ioan Todinca, editors, 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'14), volume 8747 of LNCS, pages 139-151. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-12340-0_12.
  12. Steven Chaplick, Radoslav Fulek, and Pavel Klavík. Extending partial representations of circle graphs. In Stephen K. Wismath and Alexander Wolff, editors, 21st International Symposium on Graph Drawing (GD'13), volume 8242 of LNCS, pages 131-142. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-03841-4_12.
  13. Steven Chaplick, Grzegorz Guspiel, Grzegorz Gutowski, Tomasz Krawczyk, and Giuseppe Liotta. The partial visibility representation extension problem. Algorithmica, 80(8):2286-2323, 2018. URL: https://doi.org/10.1007/s00453-017-0322-4.
  14. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  15. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  16. Giordano Da Lozzo, Giuseppe Di Battista, and Fabrizio Frati. Extending upward planar graph drawings. In Zachary Friggstad, Jörg-Rüdiger Sack, and Mohammad R. Salavatipour, editors, 16th International Symposium on Algorithms and Data Structures (WADS'19), volume 11646 of LNCS, pages 339-352. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_25.
  17. Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv., 52(1):4:1-4:37, 2019. URL: https://doi.org/10.1145/3301281.
  18. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  19. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  20. Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 49(1):1-11, 2007. URL: https://doi.org/10.1007/s00453-007-0010-x.
  21. Martin Grohe. Computing crossing numbers in quadratic time. Journal of Computer and System Sciences, 68(2):285-302, 2004. Special Issue on STOC 2001. URL: https://doi.org/10.1016/j.jcss.2003.07.008.
  22. Seok-Hee Hong and Hiroshi Nagamochi. Convex drawings of graphs with non-convex boundary constraints. Discret. Appl. Math., 156(12):2368-2380, 2008. Google Scholar
  23. Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, and Bartosz Walczak. Extending partial representations of function graphs and permutation graphs. In Leah Epstein and Paolo Ferragina, editors, 20th Annual European Symposium on Algorithms (ESA'12), volume 7501 of LNCS, pages 671-682. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_58.
  24. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, and Tomás Vyskocil. Extending partial representations of proper and unit interval graphs. Algorithmica, 77(4):1071-1104, 2017. URL: https://doi.org/10.1007/s00453-016-0133-z.
  25. Pavel Klavík, Jan Kratochvíl, Yota Otachi, and Toshiki Saitoh. Extending partial representations of subclasses of chordal graphs. Theor. Comput. Sci., 576:85-101, 2015. URL: https://doi.org/10.1016/j.tcs.2015.02.007.
  26. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, and Tomás Vyskocil. Extending partial representations of interval graphs. Algorithmica, 78(3):945-967, 2017. URL: https://doi.org/10.1007/s00453-016-0186-z.
  27. Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani. An annotated bibliography on 1-planarity. Computer Science Review, 25:49-67, 2017. URL: https://doi.org/10.1016/j.cosrev.2017.06.002.
  28. Vladimir P. Korzhik and Bojan Mohar. Minimal obstructions for 1-immersions and hardness of 1-planarity testing. Journal of Graph Theory, 72(1):30-71, 2013. URL: https://doi.org/10.1002/jgt.21630.
  29. Giuseppe Liotta and Fabrizio Montecchiani. L-visibility drawings of IC-planar graphs. Inf. Process. Lett., 116(3):217-222, 2016. URL: https://doi.org/10.1016/j.ipl.2015.11.011.
  30. Tamara Mchedlidze, Martin Nöllenburg, and Ignaz Rutter. Extending convex partial drawings of graphs. Algorithmica, 76(1):47-67, 2016. URL: https://doi.org/10.1007/s00453-015-0018-6.
  31. Kazuo Misue, Peter Eades, Wei Lai, and Kozo Sugiyama. Layout adjustment and the mental map. J. Visual Languages and Computing, 6(2):183-210, 1995. URL: https://doi.org/10.1006/jvlc.1995.1010.
  32. Maurizio Patrignani. On extending a partial straight-line drawing. Int. J. Found. Comput. Sci., 17(5):1061-1070, 2006. URL: https://doi.org/10.1142/S0129054106004261.
  33. Gerhard Ringel. Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 29(1):107-117, 1965. URL: https://doi.org/10.1007/BF02996313.
  34. Neil Robertson and Paul D. Seymour. Graph minors. III. planar tree-width. J. Comb. Theory, Ser. B, 36(1):49-64, 1984. URL: https://doi.org/10.1016/0095-8956(84)90013-3.
  35. Wanshun Yang, Weifan Wang, and Yiqiao Wang. Acyclic coloring of IC-planar graphs. Discret. Math., 342(12), 2019. URL: https://doi.org/10.1016/j.disc.2019.111623.
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 Imprint Privacy Contact