Skip to content Skip to sidebar Skip to footer
Home / drawing clustered graph using modular decomposition tree

drawing clustered graph using modular decomposition tree

Post a Comment

Years and Authors of Summarized Original Work

  • 1995; Feng, Cohen, Eades

Problem Definition

Clustered Graph Drawing, Fig. 1
figure 322

A clustered graph C(G,T) (left) and its inclusion tree (right)

Full size image

Keywords

  • Clustered graph
  • Convex drawings
  • Graph drawing
  • Planarity testing
  • Straight-line drawings

Recommended Reading

  1. Angelini P, Frati F, Kaufmann M (2011) Straight-line rectangular drawings of clustered graphs. Discret Comput Geom 45(1):88–140

    MathSciNet  MATH  CrossRef  Google Scholar

  2. Booth KS, Lueker GS (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13(3):335–379

    MathSciNet  MATH  CrossRef  Google Scholar

  3. Chimani M, Di Battista G, Frati F, Klein K (2014) Advances on testing c-planarity of embedded flat clustered graphs. In: Graph drawing (GD '14), Würzburg, pp 416–427

    Google Scholar

  4. Cortese PF, Di Battista G, Patrignani M, Pizzonia M (2005) Clustering cycles into cycles of clusters. J Graph Algorithms Appl 9(3):391–413. doi:10.7155/jgaa.00115

    Google Scholar

  5. Cortese PF, Di Battista G, Frati F, Patrignani M, Pizzonia M (2008) C-planarity of c-connected clustered graphs. J Graph Algorithms Appl 12(2):225–262

    MathSciNet  MATH  CrossRef  Google Scholar

  6. Dahlhaus E (1998) A linear time algorithm to recognize clustered graphs and its parallelization. In: Lucchesi CL, Moura AV (eds) Latin American theoretical informatics (LATIN '98), Campinas. LNCS, vol 1380. Springer, pp 239–248

    Google Scholar

  7. Di Battista G, Frati F (2009) Efficient c-planarity testing for embedded flat clustered graphs with small faces. J Graph Algorithms Appl 13(3):349–378. Special issue from GD '07

    Google Scholar

  8. Di Battista G, Tamassia R (1996) On-line planarity testing. SIAM J Comput 25:956–997

    MathSciNet  MATH  CrossRef  Google Scholar

  9. Di Battista G, Tamassia R, Tollis IG (1992) Area requirement and symmetry display of planar upward drawings. Discret Comput Geom 7: 381–401

    MathSciNet  MATH  CrossRef  Google Scholar

  10. Feng Q, Cohen RF, Eades P (1995) How to draw a planar clustered graph. In: Du D, Li M (eds) Computing and combinatorics conference (COCOON '95), Xi'an. LNCS, vol 959. Springer, pp 21–30

    Google Scholar

  11. Feng Q, Cohen RF, Eades P (1995) Planarity for clustered graphs. In: Spirakis P (ed) European symposium on algorithms (ESA '95), Corfu. LNCS, vol 979. Springer, pp 213–226

    Google Scholar

  12. Goodrich MT, Lueker GS, Sun JZ (2006) C-planarity of extrovert clustered graphs. In: Healy P, Nikolov N (eds) International symposium on graph drawing (GD '05), Limerick. LNCS, vol 3843. Springer, pp 211–222

    Google Scholar

  13. Gutwenger C, Jünger M, Leipert S, Mutzel P, Percan M, Weiskircher R (2002) Advances in c-planarity testing of clustered graphs. In: Goodrich MT, Kobourov SG (eds) International symposium on graph drawing (GD '02), Irvine. LNCS, vol 2528. Springer, pp 220–235

    Google Scholar

  14. Hong SH, Nagamochi H (2010) Convex drawings of hierarchical planar graphs and clustered planar graphs. J Discret Algorithms 8(3): 282–295

    MathSciNet  MATH  CrossRef  Google Scholar

  15. Jelínek V, Jelínková E, Kratochvíl J, Lidický B (2009) Clustered planarity: embedded clustered graphs with two-component clusters. In: Tollis IG, Patrignani M (eds) Graph drawing (GD '08), Heraklion. LNCS, vol 5417, pp 121–132. doi:10.1007/978-3-642-00219-9_13

    Google Scholar

  16. Jelínková E, Kára J, Kratochvíl J, Pergel M, Suchý O, Vyskocil T (2009) Clustered planarity: small clusters in cycles and Eulerian graphs. J Graph Algorithms Appl 13(3):379–422

    MathSciNet  MATH  CrossRef  Google Scholar

  17. Schaefer M (2013) Toward a theory of planarity: Hanani-Tutte and planarity variants. J Graph Algorithms Appl 17(4):367–440

    MathSciNet  MATH  CrossRef  Google Scholar

Download references

Author information

Authors and Affiliations

  1. School of Information Technologies, The University of Sydney, Sydney, NSW, Australia

    Fabrizio Frati

  2. Engineering Department, Roma Tre University, Rome, Italy

    Fabrizio Frati

Corresponding author

Correspondence to Fabrizio Frati .

Editor information

Editors and Affiliations

  1. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA

    Ming-Yang Kao

Rights and permissions

Copyright information

© 2016 Springer Science+Business Media New York

About this entry

Cite this entry

Frati, F. (2016). Clustered Graph Drawing. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_655

Download citation

  • .RIS
  • .ENW
  • .BIB

  • DOI : https://doi.org/10.1007/978-1-4939-2864-4_655

  • Published:

  • Publisher Name: Springer, New York, NY

  • Print ISBN: 978-1-4939-2863-7

  • Online ISBN: 978-1-4939-2864-4

  • eBook Packages: Computer Science Reference Module Computer Science and Engineering

conardweland1958.blogspot.com

Source: https://link.springer.com/referenceworkentry/10.1007/978-1-4939-2864-4_655

Post a Comment for "drawing clustered graph using modular decomposition tree"