Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/2790174.2790183guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
research-article
Free access

Practical experience with Hanani-Tutte for testing c-planarity

Published: 05 January 2014 Publication History

Abstract

We propose an algorithm for c-planarity testing which is correct and efficient, but not, in general, complete, i.e., there are input instances on which the algorithm declines to give an answer. At the core of this algorithm is an algebraic criterion based on work by the third author [20] with the following properties: (1) The criterion is a necessary condition for c-planarity, (2) for special graph classes, including c-connected graphs, the condition is also sufficient, and (3) the criterion can be tested efficiently in polynomial time. The algebraic criterion is not sufficient in general; however, we can extend it to a (still efficient) algorithm that verifies the answer of the criterion by building a c-planar embedding of the input graph. Our practical experiments show that this algorithm works well in practice. This is the first time that all instances from state-of-the-art benchmark sets for testing c-planarity are solved correctly. The algorithm is conceptually very simple and easy to implement.

References

[1]
M. Chimani, C. Gutwenger, M. Jansen, K. Klein, and P. Mutzel. Computing maximum c-planar subgraphs. In GD '09, volume 5849 of LNCS, pages 114--120. Springer, 2009.
[2]
M. Chimani, C. Gutwenger, M. Jünger, G. W. Klau, K. Klein, and P. Mutzel. The Open Graph Drawing Framework (OGDF). In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 17, pages 543--569. CRC Press, 2013.
[3]
M. Chimani and K. Klein. Shrinking the search space for clustered planarity. In GD'12, volume 7704 of LNCS, pages 90--101. Springer, 2013.
[4]
C. Chojnacki (Haim Hanani). Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae, 23:135--142, 1934.
[5]
P. F. Cortese, G. D. Battista, F. Frati, M. Patrignani, and M. Pizzonia. C-planarity of c-connected clustered graphs. J. Graph Algorithms Appl., 12(2):225--262, 2008.
[6]
P. F. Cortese, G. Di Battista, M. Patrignani, and M. Pizzonia. Clustering cycles into cycles of clusters. In GD '04, volume 3383 of LNCS, pages 100--110. Springer, 2004.
[7]
E. Dahlhaus. A linear time algorithm to recognize clustered planar graphs and its parallelization. In LATIN '98, volume 1380 of LNCS, pages 239--248. Springer, 1998.
[8]
E. Dahlhaus, K. Klein, and P. Mutzel. Planarity testing for c-connected clustered graphs. Technical Report SYS-1/06, Dep. of CS, LS 11, University Dortmund, 2006. See http://ls11-www.cs.uni-dortmund.de/_media/techreports/tr06-01.pdf.
[9]
G. Di Battista and F. Frati. Efficient c-planarity testing for embedded flat clustered graphs with small faces. In GD '07, volume 4875 of LNCS, pages 291--302. Springer, 2007.
[10]
Q. W. Feng, R. F. Cohen, and P. Eades. Planarity for clustered graphs. In ESA '95, volume 979 of LNCS, pages 213--226. Springer, 1995.
[11]
R. Fulek, J. Kynčl, I. Malinović, and D. Pálvölgyi. Efficient c-planarity testing algebraically. ArXiv e-prints, May 2013.
[12]
R. Fulek, M. Pelsmajer, M. Schaefer, and D. Štefankovič. Hanani-Tutte, monotone drawings, and level-planarity. In J. Pach, editor, Thirty Essays on Geometric Graph Theory, pages 263--287. Springer, 2012.
[13]
C. Gutwenger, M. Jünger, S. Leipert, P. Mutzel, M. Percan, and R. Weiskircher. Advances in cplanarity testing of clustered graphs. In GD '02, volume 2528 of LNCS, pages 220--235. Springer, 2002.
[14]
E. Jelínková, J. Kára, J. Kratochvíl, M. Pergel, O. Suchý, and T. Vyskocil. Clustered planarity: Small clusters in cycles and eulerian graphs. J. Graph Algorithms Appl., 13(3):379--422, 2009.
[15]
R. B. Levow. On Tutte's algebraic approach to the theory of crossing numbers. In F. Hoffman, R. B. Levow, and R. S. D. Thomas, editors, Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory and Computing, pages 315--314, Boca Raton, Fla., 1972. Florida Atlantic University.
[16]
J. Pach and G. Tóth. Monotone drawings of planar graphs. J. Graph Theory, 46(1):39--47, 2004.
[17]
J. Pach and G. Tóth. Monotone crossing number. In GD '11, volume 7034 of LNCS, pages 278--289. Springer, 2012.
[18]
M. J. Pelsmajer, M. Schaefer, and D. Stasi. Strong Hanani--Tutte on the projective plane. SIAM Journal on Discrete Mathematics, 23(3):1317--1323, 2009.
[19]
M. Schaefer. Hanani-Tutte and related results. In I. Bárány, K. J. Böröczky, G. F. Tóth, and J. Pach, editors, Geometry---Intuitive, Discrete, and Convex---A Tribute to László Fejes Tóth, Bolyai Society Mathematical Studies. Springer, 2013. To appear.
[20]
M. Schaefer. Toward a theory of planarity: Hanani-Tutte and planarity variants. Journal of Graph Algortihms and Applications, 17(4):367--440, 2013.
[21]
W. T. Tutte. Toward a theory of crossing numbers. J. Combinatorial Theory, 8:45--53, 1970.

Cited By

View all
  • (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
  • (2014)Picking Planar Edges; or, Drawing a Graph with a Planar SubgraphRevised Selected Papers of the 22nd International Symposium on Graph Drawing - Volume 887110.1007/978-3-662-45803-7_2(13-24)Online publication date: 24-Sep-2014

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings
Proceedings of the Meeting on Algorithm Engineering & Expermiments
January 2014
165 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 05 January 2014

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)37
  • Downloads (Last 6 weeks)9
Reflects downloads up to 20 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (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
  • (2014)Picking Planar Edges; or, Drawing a Graph with a Planar SubgraphRevised Selected Papers of the 22nd International Symposium on Graph Drawing - Volume 887110.1007/978-3-662-45803-7_2(13-24)Online publication date: 24-Sep-2014

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media