Document Open Access Logo

Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts

Authors Fabian Klute, Martin Nöllenburg

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.53.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Fabian Klute
Martin Nöllenburg

Cite As Get BibTex

Fabian Klute and Martin Nöllenburg. Minimizing Crossings in Constrained Two-Sided Circular Graph Layouts. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.53

Abstract

Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k >= 1, extending the previously studied case k=0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k=1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k=1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm.

Subject Classification

Keywords
  • Graph Drawing
  • Circular Layouts
  • Crossing Minimization
  • Circle Graphs
  • Bounded-Degree Maximum-Weight Induced Subgraphs

Metrics

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

References

  1. Md Jawaherul Alam, Martin Fink, and Sergey Pupyrev. The bundled crossing number. In Y. Hu and M. Nöllenburg, editors, Graph Drawing and Network Visualization (GD'16), volume 9801 of LNCS, pages 399-412. Springer, 2016. Google Scholar
  2. Michael Baur and Ulrik Brandes. Crossing reduction in circular layouts. In Graph-Theoretic Concepts in Computer Science (WG'04), volume 3353 of LNCS, pages 332-343. Springer, 2004. Google Scholar
  3. Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann. On bounded-degree vertex deletion parameterized by treewidth. Discrete Applied Mathematics, 160(1-2):53-60, 2012. Google Scholar
  4. Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W Klau, Karsten Klein, and Petra Mutzel. The open graph drawing framework (OGDF). In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 17, pages 543-569. CRC Press, 2013. Google Scholar
  5. Anders Dessmark, Klaus Jansen, and Andrzej Lingas. The maximum k-dependent and f-dependent set problem. In K. W. Ng, P. Raghavan, N. V. Balasubramanian, and F. Y. L. Chin, editors, Algorithms and Computation (ISAAC'93), volume 762 of LNCS, pages 88-97. Springer, 1993. Google Scholar
  6. Fedor V Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM J. Computing, 44(1):54-87, 2015. Google Scholar
  7. Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. In Theoretical Aspects of Computer Science (STACS'18), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:14, 2018. Google Scholar
  8. Emden R Gansner and Yehuda Koren. Improved circular layouts. In Graph Drawing (GD'06), volume 4372 of LNCS, pages 386-398. Springer, 2007. Google Scholar
  9. Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, and Ioan Todinca. Exponential time algorithms for the minimum dominating set problem on some graph classes. ACM Trans. Algorithms, 6(1):9:1-9:21, 2009. Google Scholar
  10. Fanika Gavril. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks, 3(3):261-273, 1973. Google Scholar
  11. Michael Jünger and Petra Mutzel, editors. Graph Drawing Software. Mathematics and Visualization. Springer, 2004. Google Scholar
  12. J Mark Keil. The complexity of domination problems in circle graphs. Discrete Applied Mathematics, 42(1):51-63, 1993. Google Scholar
  13. Jonathan Klawitter, Tamara Mchedlidze, and Martin Nöllenburg. Experimental evaluation of book drawing algorithms. In F. Frati and K.-L. Ma, editors, Graph Drawing and Network Visualization (GD'17), volume 10692 of LNCS, pages 224-238. Springer, 2018. URL: https://arxiv.org/abs/1708.09221.
  14. Ton Kloks. Treewidth of circle graphs. International J. Foundations of Computer Science, 7(02):111-120, 1996. Google Scholar
  15. Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani. An annotated bibliography on 1-planarity. CoRR, abs/1703.02261, 2017. URL: http://arxiv.org/abs/1703.02261.
  16. Martin I. Krzywinski, Jacqueline E. Schein, Inanc Birol, Joseph Connors, Randy Gascoyne, Doug Horsman, Steven J. Jones, and Marco A. Marra. Circos: An information aesthetic for comparative genomics. Genome Research, 19:1639-1645, 2009. Google Scholar
  17. Giuseppe Liotta. Graph drawing beyond planarity: some results and open problems. In Italian Conference on Theoretical Computer Science (ICTCS'14), pages 3-8, 2014. Google Scholar
  18. Sumio Masuda, Toshinobu Kashiwabara, Kazuo Nakajima, and Toshio Fujisawa. On the NP-completeness of a computer network layout problem. In Circuits and Systems (ISCAS'87), pages 292-295. IEEE, 1987. Google Scholar
  19. Sumio Masuda, Kazuo Nakajima, Toshinobu Kashiwabara, and Toshio Fujisawa. Crossing minimization in linear embeddings of graphs. IEEE Trans. Computers, 39(1):124-127, 1990. Google Scholar
  20. Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, and Imrich Vrt'o. The book crossing number of a graph. J. Graph Theory, 21(4):413-424, 1996. Google Scholar
  21. Janet M. Six and Ioannis G. Tollis. Circular drawing algorithms. In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 9, pages 285-315. CRC Press, 2013. Google Scholar
  22. Wolfgang Thomas. Languages, automata, and logic. Handbook of formal languages, 3:389-455, 1996. Google Scholar
  23. Gabriel Valiente. A new simple algorithm for the maximum-weight independent set problem on circle graphs. In Algorithms and Computation (ISAAC'03), volume 2906 of LNCS, pages 129-137. Springer, 2003. Google Scholar
  24. Mihalis Yannakakis. Node- and edge-deletion NP-complete problems. In Theory of Computing (STOC'78), pages 253-264. ACM, 1978. 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