Article

Clustered planarity

Authors:

Pier Francesco Cortese,

Giuseppe Di BattistaAuthors Info & Claims

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

Pages 32 - 34

https://doi.org/10.1145/1064092.1064093

Published: 06 June 2005 Publication History

Get Access

References

[1]

T. C. Biedl, M. Kaufmann, and P. Mutzel. Drawing planar partitions II: HH-Drawings. In Workshop on Graph-Theoretic Concepts in Computer Science (WG'98), volume 1517, pages 124--136. Springer-Verlag, 1998.

Digital Library

Google Scholar

[2]

S. Cornelsen and D. Wagner. Completely connected clustered graphs. In Proc. 29th Intl. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), volume 2880 of LNCS, pages 168--179. Springer-Verlag, 2003.

Crossref

Google Scholar

[3]

P. F. Cortese, G. Di Battista, M. Patrignani, and M. Pizzonia. Clustering cycles into cycles of clusters. In J. Pach, editor, Proc. Graph Drawing 2004 (GD'04), volume 3383 of LNCS, pages 100--110. Springer-Verlag, 2004.

Digital Library

Google Scholar

[4]

E. Dahlhaus. Linear time algorithm to recognize clustered planar graphs and its parallelization. In C. Lucchesi, editor, LATIN '98, 3rd Latin American symposium on theoretical informatics, Campinas, Brazil, April 20--24, 1998, volume 1380 of LNCS, pages 239--248, 1998.

Digital Library

Google Scholar

[5]

G. Di Battista, W. Didimo, and A. Marcandalli. Planarization of clustered graphs. In Proc. Graph Drawing 2001 (GD'01), LNCS, pages 60--74. Springer-Verlag, 2001.

Digital Library

Google Scholar

[6]

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

Google Scholar

[7]

G. Di Battista, W. P. Liu, and I. Rival. Bipartite graphs, upward drawings, and planarity. Information Processign Letters, 36(6):317--322, 1990.

Digital Library

Google Scholar

[8]

C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Planarity-preserving clustering and embedding for large planar graphs. J. Computational Geometry, 24(2):95--114, 2003.

Digital Library

Google Scholar

[9]

P. Eades and Q. W. Feng. Multilevel visualization of clustered graphs. In S. C. North, editor, Proc. Graph Drawing 1996 (GD'96), volume 1190 of LNCS, pages 101--112. Springer-Verlag, 1997.

Digital Library

Google Scholar

[10]

P. Eades, Q. W. Feng, and X. Lin. Straight line drawing algorithms for hierarchical graphs and clustered graphs. In S. C. North, editor, Proc. Graph Drawing 1996 (GD'96), volume 1190 of LNCS, pages 113--128. Springer-Verlag, 1997.

Digital Library

Google Scholar

[11]

P. Eades, Q.-W. Feng, and H. Nagamochi. Drawing clustered graphs on an orthogonal grid. J. Graph Algorithms Appl., 3(4):3--29, 1999.

Crossref

Google Scholar

[12]

Q. Feng. Algorithms for Drawing Clustered Graphs. PhD thesis, Department of Computer Science and Software engineering, University of Newclastle, Apr. 1997.

Google Scholar

[13]

Q. W. Feng, R. F. Cohen, and P. Eades. Planarity for clustered graphs. In P. Spirakis, editor, Symposium on Algorithms (Proc. ESA '95), volume 979 of LNCS, pages 213--226. Springer-Verlag, 1995.

Digital Library

Google Scholar

[14]

C. Gutwenger, M. Jnger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher. Subgraph induced planar connectivity augmentation. In 29-th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), volume 2880 of LNCS, pages 261--272. Springer-Verlag, 2003.

Google Scholar

[15]

C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher. Advances in C-planarity testing of clustered graphs. In S. G. Kobourov and M. T. Goodrich, editors, Proc. Graph Drawing 2002 (GD'02), volume 2528 of LNCS, pages 220--235. Springer-Verlag, 2002.

Digital Library

Google Scholar

[16]

T. Lengauer. Hierarchical planarity testing algorithms. J. ACM, 36(3):474--509, 1989.

Digital Library

Google Scholar

[17]

H. Nagamochi and K. Kuroya. Convex drawing for c-planar biconnected clustered graphs. In G. Liotta, editor, Proc. Graph Drawing 2003 (GD'03), volume 2912 of LNCS, pages 369--380. Springer-Verlag, 2004.

Google Scholar

Cited By

View all

Liotta GRutter ITappini A(2023)Parameterized complexity of graph planarity with restricted cyclic ordersJournal of Computer and System Sciences10.1016/j.jcss.2023.02.007135:C(125-144)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.jcss.2023.02.007
Liotta GRutter ITappini A(2022)Parameterized Complexity of Graph Planarity with Restricted Cyclic OrdersGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-15914-5_28(383-397)Online publication date: 1-Oct-2022
https://doi.org/10.1007/978-3-031-15914-5_28
Da Lozzo GEppstein DGoodrich MGupta S(2021)C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-WidthAlgorithmica10.1007/s00453-021-00839-2Online publication date: 8-Jun-2021
https://doi.org/10.1007/s00453-021-00839-2
Show More Cited By

Index Terms

Clustered planarity
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Relaxing the constraints of clustered planarity

In a drawing of a clustered graph vertices and edges are drawn as points and curves, respectively, while clusters are represented by simple closed regions. A drawing of a clustered graph is c-planar if it has no edge-edge, edge-region, or region-region ...
Planarity of streamed graphs
Abstract
In this paper we introduce a notion of planarity for graphs that are presented in a streaming fashion. A streamed graph is a stream of edges e 1 , e 2 , … , e m on a vertex set V. A streamed graph is ω-stream planar with respect to a ...
On the Planar Split Thickness of Graphs

Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at ...

Comments

Information & Contributors

Information

Published In

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

June 2005

398 pages

ISBN:1581139918

DOI:10.1145/1064092

Program Chairs:
Joe Mitchell
SUNY Stony Brook
,
Günter Rote
Freie Universität Berlin

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG05

Sponsor:

SoCG05: The 21st Annual ACM Symposium on Computational Geometry 2005

June 6 - 8, 2005

Pisa, Italy

Acceptance Rates

SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
433
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liotta GRutter ITappini A(2023)Parameterized complexity of graph planarity with restricted cyclic ordersJournal of Computer and System Sciences10.1016/j.jcss.2023.02.007135:C(125-144)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.jcss.2023.02.007
Liotta GRutter ITappini A(2022)Parameterized Complexity of Graph Planarity with Restricted Cyclic OrdersGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-15914-5_28(383-397)Online publication date: 1-Oct-2022
https://doi.org/10.1007/978-3-031-15914-5_28
Da Lozzo GEppstein DGoodrich MGupta S(2021)C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-WidthAlgorithmica10.1007/s00453-021-00839-2Online publication date: 8-Jun-2021
https://doi.org/10.1007/s00453-021-00839-2
Fulek RTóth CChawla S(2020)Atomic embeddability, clustered planarity, and thickenabilityProceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3381089.3381264(2876-2895)Online publication date: 5-Jan-2020
https://dl.acm.org/doi/10.5555/3381089.3381264
Eppstein D(2020)Treetopes and Their GraphsDiscrete & Computational Geometry10.1007/s00454-020-00177-0Online publication date: 25-Jan-2020
https://doi.org/10.1007/s00454-020-00177-0
Didimo WLiotta GMontecchiani F(2019)A Survey on Graph Drawing Beyond PlanarityACM Computing Surveys10.1145/330128152:1(1-37)Online publication date: 21-Feb-2019
https://dl.acm.org/doi/10.1145/3301281
Cortese PPatrignani M(2018)Clustered Planarity = Flat Clustered PlanarityGraph Drawing and Network Visualization10.1007/978-3-030-04414-5_2(23-38)Online publication date: 18-Dec-2018
https://doi.org/10.1007/978-3-030-04414-5_2
Eppstein D(2016)Treetopes and their graphsProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884504(969-984)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884504
Fulek RKynčl JMalinović IPálvölgyi D(2014)Clustered Planarity Testing RevisitedRevised Selected Papers of the 22nd International Symposium on Graph Drawing - Volume 887110.1007/978-3-662-45803-7_36(428-439)Online publication date: 24-Sep-2014
https://dl.acm.org/doi/10.1007/978-3-662-45803-7_36
Fulek R(2014)Towards the Hanani-Tutte Theorem for Clustered GraphsGraph-Theoretic Concepts in Computer Science10.1007/978-3-319-12340-0_15(176-188)Online publication date: 21-Oct-2014
https://doi.org/10.1007/978-3-319-12340-0_15
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

References

Cited By

Index Terms

Recommendations

Relaxing the constraints of clustered planarity

Planarity of streamed graphs

On the Planar Split Thickness of Graphs

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations