Document Open Access Logo

Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph

Authors Michal Kotrbcík, Martin Skoviera

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.14.pdf
  • Filesize: 380 kB
  • 9 pages

Document Identifiers

Author Details

Michal Kotrbcík
Martin Skoviera

Cite As Get BibTex

Michal Kotrbcík and Martin Skoviera. Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.14

Abstract

The maximum genus gamma_M(G) of a graph G is the largest genus of an orientable surface into which G has a cellular embedding. Combinatorially, it coincides with the maximum number of disjoint pairs of adjacent edges of G whose removal results in a connected spanning subgraph of G. In this paper we describe a greedy 2-approximation algorithm for maximum genus by proving that removing pairs of adjacent edges from G arbitrarily while retaining connectedness leads to at least gamma_M(G)/2 pairs of edges removed. As a consequence of our approach we also obtain a 2-approximate counterpart of Xuong's combinatorial characterisation of maximum genus.

Subject Classification

Keywords
  • maximum genus
  • embedding
  • graph
  • greedy algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Archdeacon, C. P. Bonnington, and J. Širáň. A Nebeský-Type Characterization for Relative Maximum Genus. J. Combin. Theory Ser. B, 73(1):77-98, 1998. Google Scholar
  2. D. Archdeacon, M. Kotrbčík, R. Nedela, and M. Škoviera. Maximum genus, connectivity, and Nebeský’s Theorem. Ars Math. Contemp., 9:51-61, 2015. Google Scholar
  3. L. W. Beineke, R. J. Wilson, J. L. Gross, and T. W. Tucker, editors. Topics in Topological Graph Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009. Google Scholar
  4. S. Beyer, M. Chimani, I. Hedtke, and M. Kotrbčík. A Practical Method for the Minimum Genus of a Graph: Models and Experiments. In A. V. Goldberg and A. S. Kulikov, editors, Proceedings of 15th International Symposium on Experimental Algorithms SEA'16, pages 75-88. Springer International Publishing, 2016. Google Scholar
  5. J. Chen. Algorithmic graph embeddings. Theoret. Comput. Sci., 181:247-266, 1997. Google Scholar
  6. J. Chen, D. Archdeacon, and J. L. Gross. Maximum genus and connectivity. Discrete Math., 149:19-29, 1996. Google Scholar
  7. J. Chen, S. P. Kanchi, and A. Kanevsky. On the Complexity of Graph Embeddings (extended abstract). In F. Dehme et. al., editor, Algorithms and Data Structures WADS'93, volume 709 of Lecture Notes in Comp. Sci., pages 234-245. Springer-Verlag, Berlin, 1993. Google Scholar
  8. J. Chen, S. P. Kanchi, and A. Kanevsky. On the Complexity of Graph Embeddings (extended abstract). In F. Dehme et al., editor, Algorithms and Data Structures, volume 709 of Lecture Notes in Comp. Sci., pages 234-245. Springer-Verlag, Berlin, 1993. Google Scholar
  9. J. Chen, S. P. Kanchi, and A. Kanevsky. A note on approximating graph genus. Inform. Process. Lett., 6(61):317-322, 1997. Google Scholar
  10. H. Y. Cheung, L. C. Lau, and K. M. Leung. Algebraic Algorithms for Linear Matroid Parity Problems. ACM Trans. Algorithms, 10(3):10:1-10:26, 2014. Google Scholar
  11. D. de Caen. An upper bound on the sum of squares of degrees in a graph. Discrete Math., 185(1-3):245-248, 1998. Google Scholar
  12. R. A. Duke. The genus, regional number, and the Betti number of a graph. Canad. J. Math., 18:817-822, 1966. Google Scholar
  13. M. L. Furst, J. L. Gross, and L. A. McGeoch. Finding a maximum-genus embedding. J. ACM, 35:523-534, 1988. Google Scholar
  14. H. M. Gabow and M. Stallmann. Effecient Algorithms for Graphic Matroid Intersection and Parity (extended abstract). In Automata, Languages and Programming ICALP'85, volume 194 of LNCS, pages 210-220. Springer-Verlag, Berlin, 1985. Google Scholar
  15. M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to the theory of NP-completeness. Bell Telephone Laboratories, 1979. Google Scholar
  16. R. Giles. Optimum Matching Forests I: Special Weights. Math. Programming, 22:1-12, 1982. Google Scholar
  17. A. D. Glukhov. A contribution to the theory of maximum genus of a graph. In Structure and Topological Properties of Graphs, pages 15-29. Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1981. In Russian. Google Scholar
  18. J. L. Gross. Embeddings of graphs of fixed treewidth and bounded degree. Ars Math. Contemp., 7(2):379-403, 2014. Google Scholar
  19. J. L. Gross and M. L. Furst. Hierarchy for imbedding-distribution invariants of a graph. J. Graph Theory, 11(2):205-220, 1987. Google Scholar
  20. J. L. Gross, T. Mansour, T. W. Tucker, and D. Wang. Log-Concavity of Combinations of Sequences and Applications to Genus Distributions. SIAM J. Discrete Math., 29(2):1002-1029, 2015. Google Scholar
  21. J. L. Gross and R. G. Rieper. Local extrema in genus-stratified graphs. J. Graph Theory, 15:159-171, 1991. Google Scholar
  22. J. L. Gross and T. W. Tucker. Topological Graph Theory. Wiley, 1987. Google Scholar
  23. M. Hellmuth, A. S. Knudsen, M. Kotrbčík, D. Merkle, and N. Nøjgaard. Linear Time Canonicalization and Enumeration of Non-Isomorphic 1-Face Embeddings. In R. Pagh and S. Venkatasubramanian, editors, Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments ALENEX'18, pages 154-168. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  24. Y. Huang. Maximum genus and chromatic number of graphs. Discrete Math., 271(1):117-127, 2003. Google Scholar
  25. S. Iwata and Y. Kobayashi. A Weighted Linear Matroid Parity Algorithm. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing STOC'17, pages 264-276. ACM, 2017. Google Scholar
  26. M. Jungerman. A charactrerization of upper embeddable graphs. Trans. Amer. Math. Soc., 241:401-406, 1978. Google Scholar
  27. K. Kawarabayashi and A. Sidiropoulos. Beyond the Euler characteristic: Approximating the genus of general graphs. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing STOC'15, pages 675-682. ACM, 2015. Google Scholar
  28. N. P. Khomenko and A. D. Glukhov. Single-component 2-cell embeddings and maximum genus of a graph. In Some topological and combinatorial properties of graphs, pages 5-23. Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1980. In Russian. Google Scholar
  29. N. P. Khomenko, N. A. Ostroverkhy, and V. A. Kuzmenko. The maximum genus of a graph. In ϕ-Transformations of Graphs, pages 180-207. Inst. Mat. Akad. Nauk Ukrain. SSR, Kiev, 1973. In Ukrainian with English summary. Google Scholar
  30. S. Kundu. Bounds on Number of Disjoint Spanning Trees. J. Combinatorial Theory Ser. B, 17:199-203, 1974. Google Scholar
  31. J. Lee, M. Sviridenko, and J. Vondrák. Matroid Matching: The Power of Local Search. SIAM J. Computing, 42(1):357-379, 2013. Google Scholar
  32. L. Lovász. The matroid matching problem. In Algebraic methods in Graph Theory, volume 25 of Colloquia Mathematica Soc. János Bolyai, pages 495-517. North-Holland, Amsterdam, 1978. Google Scholar
  33. L. Lovász. Matroid matching and some applications. J. Combin. Theory Ser. B, 28(2):208-236, 1980. Google Scholar
  34. L. Lovász. Selecting independent lines from a family of lines in a space. Acta Sci. Math., 42:121-131, 1980. Google Scholar
  35. B. Mohar and C. Thomassen. Graphs on Surfaces. The Johns Hopkins University Press, 2001. Google Scholar
  36. W. Myrvold and W. Kocay. Errors in graph embedding algorithms. J. Comp. System Sci., 77(2):430-438, 2011. Google Scholar
  37. W. Myrvold and J. Woodcock. A Large Set of Torus Obstructions and How They Were Discovered. Electronic J. Combin., 25(1):♯P1.16, 2018. Google Scholar
  38. L. Nebeský. A new characterization of the maximum genus of a graph. Czechoslovak Math. J., 31(106):604-613, 1981. Google Scholar
  39. E. A. Nordhaus, R. D. Ringeisen, B. M. Stewart, and A. T. White. A Kuratowski-type theorem for the maximum genus of a graph. J. Combin. Theory Ser. B, 12:260-267, 1972. Google Scholar
  40. E. A. Nordhaus, B. M. Stewart, and A. T. White. On the maximum genus of a graph. J. Combin. Theory Ser. B, 11(3):258-267, 1971. Google Scholar
  41. J. Orlin. A Fast, Simpler Algorithm for the Matroid Parity Problem. In A. Lodi, A. Panconesi, and G. Rinaldi, editors, Integer Programming and Combinatorial Optimization, volume 5035 of Lecture notes in comp. sci., pages 240-258. Springer-Verlag, 2008. Google Scholar
  42. R. D. Ringeisen. Determining all compact orientable 2-manifolds upon which K_m,n has 2-cell imbeddings. J. Combin. Theory Ser. B, 12(2):101-104, 1972. Google Scholar
  43. R. D. Ringeisen. Survey of results on the maximum genus of a graph. J. Graph Theory, 3:1-13, 1979. Google Scholar
  44. J. Širáň and M. Škoviera. Characterization of the maximum genus of a signed graph. J. Combinatorial Theory ser. B, 52:124-146, 1991. Google Scholar
  45. M. Škoviera. The maximum genus of graphs of diameter two. Discrete Math., 52:124-146, 1991. Google Scholar
  46. S. Stahl. On the Number of Maximum Genus Embeddings of Almost all Graphs. European J. Combin., 13:119-126, 1992. Google Scholar
  47. S. Stahl. On the average genus of the random graph. J. Graph Theory, 20(1):1-18, 1995. Google Scholar
  48. C. Thomassen. The Graph Genus Problem is NP-Complete. J. Algorithms, 10:568-576, 1989. Google Scholar
  49. C. Thomassen. Bidirectional retracting-free double tracings and upper embeddability of graphs. J. Combinatorial Theory ser. B, 50(2):198-207, 1990. Google Scholar
  50. C. Thomassen. The Genus Problem for Cubic Graphs. J. Combin. Theory Ser. B, 69(1):52-58, 1997. Google Scholar
  51. C. Wulff-Nilsen. Faster Deterministic Fully-dynamic Graph Connectivity. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms SODA'13, pages 1757-1769. Society for Industrial and Applied Mathematics, 2013. Google Scholar
  52. N. H. Xuong. How to determine the maximum genus of a graph. J. Combin. Theory Ser. B, 26:217-225, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact