Imbalance, Cutwidth, and the Structure of Optimal Orderings | SpringerLink
Skip to main content
Springer Nature Link
Log in

Imbalance, Cutwidth, and the Structure of Optimal Orderings

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2019)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 11653))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

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)

    Article  MathSciNet  Google Scholar 

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

    Book  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

    Chapter  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)

    Article  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)

    Article  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)

    Article  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

    Chapter  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

    Chapter  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

    Chapter  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)

    Article  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

    Chapter  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

    Chapter  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)

    Article  MathSciNet  Google Scholar 

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

    Article  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)

    Article  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)

    Article  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)

    Article  MathSciNet  Google Scholar 

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

    Article  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)

    Article  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)

    Article  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)

    Article  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)

    Article  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)

    Article  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

Authors
  1. Jan Gorzny
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jonathan F. Buss
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jan Gorzny .

Editor information

Editors and Affiliations

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

    Ding-Zhu Du

  2. Xidian University, Xi'an, China

    Zhenhua Duan

  3. Xidian University, Xi'an, China

    Cong Tian

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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

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

  • Published:

  • Publisher Name: Springer, Cham

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

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

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics