A Global k-Level Crossing Reduction Algorithm | SpringerLink
Skip to main content

A Global k-Level Crossing Reduction Algorithm

  • Conference paper
WALCOM: Algorithms and Computation (WALCOM 2010)

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

Included in the following conference series:

Abstract

Directed graphs are commonly drawn by the Sugiyama algorithm, where crossing reduction is a crucial phase. It is done by repeated one-sided 2-level crossing minimizations, which are still \({\mathcal{NP}}\)-hard.

We introduce a global crossing reduction, which at any particular time captures all crossings, especially for long edges. Our approach is based on the sifting technique and improves the level-by-level heuristics in the hierarchic framework by a further reduction of the number of crossings by 5 – 10%. In addition it avoids type 2 conflicts which help to straighten the edges, and has a running time which is quadratic in the size of the input graph independently of dummy vertices. Finally, the approach can directly be extended to cyclic, radial, and clustered level graphs where it achieves similar improvements over the previous algorithms.

Supported by the Deutsche Forschungsgemeinschaft (DFG), grant BR835/15-1.

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

Access this chapter

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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bachmaier, C.: A radial adaption of the sugiyama framework for visualizing hierarchical information. IEEE Trans. Vis. Comput. Graphics 13(3), 583–594 (2007)

    Article  MathSciNet  Google Scholar 

  2. Bachmaier, C., Brunner, W.: Linear time planarity testing and embedding of strongly connected cyclic level graphs. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 136–147. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  3. Baur, M., Brandes, U.: Crossing reduction in circular layouts. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 332–343. Springer, Heidelberg (2004)

    Google Scholar 

  4. Brandes, U., Köpf, B.: Fast and simple horizontal coordinate assignment. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 31–44. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  5. Eades, P., Kelly, D.: Heuristics for reducing crossings in 2-layered networks. Ars Combinatorica 21(A), 89–98 (1986)

    MathSciNet  Google Scholar 

  6. Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(1), 379–403 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  7. Eiglsperger, M., Siebenhaller, M., Kaufmann, M.: An efficient implementation of sugiyama’s algorithm for layered graph drawing. J. Graph Alg. App. 9(3), 305–325 (2005)

    MATH  MathSciNet  Google Scholar 

  8. Jünger, M., Lee, E.K., Mutzel, P., Odenthal, T.: A polyhedral approach to the multi-layer crossing minimization problem. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 13–24. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  9. Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)

    MATH  Google Scholar 

  10. Matuszewski, C., Schönfeld, R., Molitor, P.: Using sifting for k-layer straightline crossing minimization. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 217–224. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  11. Rudell, R.: Dynamic variable ordering for ordered binary decision diagrams. In: Proc. IEEE/ACM International Conference on Computer Aided Design, ICCAD 1993, pp. 42–47. IEEE Computer Society Press, Los Alamitos (1993)

    Google Scholar 

  12. Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst., Man, Cybern. 11(2), 109–125 (1981)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bachmaier, C., Brandenburg, F.J., Brunner, W., Hübner, F. (2010). A Global k-Level Crossing Reduction Algorithm. In: Rahman, M.S., Fujita, S. (eds) WALCOM: Algorithms and Computation. WALCOM 2010. Lecture Notes in Computer Science, vol 5942. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11440-3_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-11440-3_7

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-11439-7

  • Online ISBN: 978-3-642-11440-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics