Using Cutwidth and Then Geomcol for Continuous

Abstract

We show that both Cutwidth and Imbalance are fixed-parameter tractable when parameterized by the twin-cover number of the input graph. We further show that Imbalance is NP-complete for split graphs and therefore chordal graphs, but linear-time solvable for proper interval graphs, which equals the complexity of Cutwidth on these classes.

Both results follow from a new structural theorem, that every instance of Cutwidth or Imbalance has an optimal ordering of a restricted form.

Keywords

• Imbalance
• Cutwidth
• Twin-cover
• Vertex layout
• Proper interval graph
• Split graph

Notes

1. 1.

   The statements marked with a * are proved in the full version of the paper.

References

1. Bakken, O.R.: Arrangement problems parameterized by neighbourhood diversity. Master's thesis, The University of Bergen (2018)

   Google Scholar

2. Biedl, T., Chan, T., Ganjali, Y., Hajiaghayi, M.T., Wood, D.R.: Balanced vertex-orderings of graphs. Discrete Appl. Math. 148(1), 27–48 (2005)

   CrossRef  MathSciNet  Google Scholar

3. Brandstadt, A., Spinrad, J.P., et al.: Graph Classes: A Survey, vol. 3. SIAM, Philadelphia (1999)

   CrossRef  Google Scholar

4. Charbit, P., Habib, M., Mouatadid, L., Naserasr, R.: A new graph parameter to measure linearity. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017. LNCS, vol. 10628, pp. 154–168. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71147-8_11

   CrossRef  Google Scholar

5. Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl. Math. 138(3), 371–379 (2004)

   CrossRef  MathSciNet  Google Scholar

6. Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs. SIAM J. Discrete Math. 23(4), 1905–1953 (2009)

   CrossRef  MathSciNet  Google Scholar

7. Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On cutwidth parameterized by vertex cover. Algorithmica 68(4), 940–953 (2014)

   CrossRef  MathSciNet  Google Scholar

8. Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 294–305. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92182-0_28

   CrossRef  Google Scholar

9. Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163–176. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03898-8_15

   CrossRef  MATH  Google Scholar

10. Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 259–271. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28050-4_21

    CrossRef  MATH  Google Scholar

11. Gaspers, S., Messinger, M.-E., Nowakowski, R.J., Prałat, P.: Clean the graph before you draw it!. Inf. Process. Lett. 109(10), 463–467 (2009)

    CrossRef  MathSciNet  Google Scholar

12. Giannopoulou, A.C., Pilipczuk, M., Raymond, J.-F., Thilikos, D.M., Wrochna, M.: Cutwidth: obstructions and algorithmic aspects. arXiv preprint arXiv:1606.05975 (2016)

13. Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of split graphs, threshold graphs, and proper interval graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 218–229. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92248-3_20

    CrossRef  Google Scholar

14. Heggernes, P., van 't Hof, P., Lokshtanov, D., Nederlof, J.: Computing the cutwidth of bipartite permutation graphs in linear time. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 75–87. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16926-7_9

    CrossRef  MATH  Google Scholar

15. Jinjiang, Y., Liying, K.: One characterization of unit interval graphs and its applications. J. Shijiazhuang Railway Inst. 7(2), 50–54 (1994)

    Google Scholar

16. Jinjiang, Y., Sanming, Z.: Optimal labelling of unit interval graphs. Appl. Math. 10(3), 337–344 (1995)

    CrossRef  MathSciNet  Google Scholar

17. Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)

    CrossRef  MathSciNet  Google Scholar

18. Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci. 172(1–2), 175–193 (1997)

    CrossRef  MathSciNet  Google Scholar

19. Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51(1), 45–64 (1962)

    CrossRef  MathSciNet  Google Scholar

20. Lilleeng, S.: A polynomial-time solvable case for the NP-hard problem cutwidth. Master's thesis, The University of Bergen (2014)

    Google Scholar

21. Lokshtanov, D., Misra, N., Saurabh, S.: Imbalance is fixed parameter tractable. Inf. Process. Lett. 113(19–21), 714–718 (2013)

    CrossRef  MathSciNet  Google Scholar

22. Papakostas, A., Tollis, I.G.: Algorithms for area-efficient orthogonal drawings. Comput. Geom. 9(1–2), 83–110 (1998)

    CrossRef  MathSciNet  Google Scholar

23. Stephane, F., Hammer, P.L.: Split graphs. In: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 311–315 (1977)

    Google Scholar

24. Thilikos, D.M., Serna, M., Bodlaender, H.L.: Cutwidth I: a linear time fixed parameter algorithm. J. Algorithms 56(1), 1–24 (2005)

    CrossRef  MathSciNet  Google Scholar

25. Thilikos, D.M., Serna, M., Bodlaender, H.L.: Cutwidth II: algorithms for partial w-trees of bounded degree. J. Algorithms 56(1), 25–49 (2005)

    CrossRef  MathSciNet  Google Scholar

26. Wagner, G.: Eigenschaften der nerven homologische-einfactor familien in \(R^n\). Ph.D. thesis, Universität Gottigen (1967)

    Google Scholar

27. Wood, D.R.: Optimal three-dimensional orthogonal graph drawing in the general position model. Theoret. Comput. Sci. 299(1–3), 151–178 (2003)

    CrossRef  MathSciNet  Google Scholar

28. Wood, D.R.: Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout. Algorithmica 39(3), 235–253 (2004)

    CrossRef  MathSciNet  Google Scholar

29. Wood, D.R., Kratochvil, J., Kára, J.: On the complexity of the balanced vertex ordering problem. Discrete Math. Theor. Comput. Sci. 9 (2007)

    Google Scholar

30. Yannakakis, M.: A polynomial algorithm for the min-cut linear arrangement of trees. J. ACM (JACM) 32(4), 950–988 (1985)

    CrossRef  MathSciNet  Google Scholar

Download references

Acknowledgements

The authors would like to thank Therese Biedl for helpful conversations on these results, as well as the anonymous reviewers for their suggestions.

Author information

Authors and Affiliations

1. University of Waterloo, Waterloo, ON, Canada

   Jan Gorzny & Jonathan F. Buss

Corresponding author

Correspondence to Jan Gorzny .

Editor information

Editors and Affiliations

1. The University of Texas at Dallas, Richardson, TX, USA

   Dr. Ding-Zhu Du

2. Xidian University, Xi'an, China

   Prof. Zhenhua Duan

3. Xidian University, Xi'an, China

   Cong Tian

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Cite this paper

Gorzny, J., Buss, J.F. (2019). Imbalance, Cutwidth, and the Structure of Optimal Orderings. In: Du, DZ., Duan, Z., Tian, C. (eds) Computing and Combinatorics. COCOON 2019. Lecture Notes in Computer Science(), vol 11653. Springer, Cham. https://doi.org/10.1007/978-3-030-26176-4_18

Download citation

• .RIS
• .ENW
• .BIB

• DOI : https://doi.org/10.1007/978-3-030-26176-4_18

• Published: 21 July 2019

• Publisher Name: Springer, Cham

• Print ISBN: 978-3-030-26175-7

• Online ISBN: 978-3-030-26176-4

• eBook Packages: Computer Science Computer Science (R0)

sheltonandp1997.blogspot.com

Source: https://link.springer.com/chapter/10.1007/978-3-030-26176-4_18

Share this post