Abstract
A matching is a set of edges without common endpoint. It was recently shown that every 1-planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per edge) that has minimum degree 3 has a matching of size at least \(\frac{n+12}{7}\), and this is tight for some graphs. The proof did not come with an algorithm to find the matching more efficiently than a general-purpose maximum-matching algorithm. In this paper, we give such an algorithm. More generally, we show that any matching that has no augmenting paths of length 9 or less has size at least \(\frac{n+12}{7}\) in a 1-planar graph with minimum degree 3.
F. Klute—This work was conducted while FK was a member of the “Algorithms and Complexity Group” at TU Wien.
Research of TB supported by NSERC. Research initiated while FK was visiting the University of Waterloo.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In this paper, ‘minimum degree k’ stands for ‘minimum degree at least k’; of course the bounds also hold if all degrees are higher.
- 2.
Our terminology follows the one in Edmonds’ famous blossom-algorithm [12].
References
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994). https://doi.org/10.1145/174644.174650
Bast, H., Mehlhorn, K., Schäfer, G., Tamaki, H.: Matching algorithms are fast in sparse random graphs. Theor. Comput. Syst. 39(1), 3–14 (2006). https://doi.org/10.1007/s00224-005-1254-y
Berge, C.: Graphs and Hypergraphs, 2nd edn. North-Holland (1976). Translated from Graphes et Hypergraphes, Dunod (1970)
Biedl, T., Bose, P., Demaine, E.D., Lubiw, A.: Efficient algorithms for Petersen’s matching theorem. J. Algorithms 38(1), 110–134 (2001). https://doi.org/10.1006/jagm.2000.1132
Biedl, T., Klute, F.: Finding large matchings in 1-planar graphs of minimum degree 3 (2020). CoRR 2002.11818. http://arxiv.org/abs/2002.11818
Biedl, T., Wittnebel, J.: Matchings in 1-planar graphs with large minimum degree (2019). CoRR 1911.04603. http://arxiv.org/abs/1911.04603
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335–379 (1976). https://doi.org/10.1016/S0022-0000(76)80045-1
Chiba, N., Nishizeki, T.: The Hamiltonian cycle problem is linear-time solvable for \(4\)-connected planar graphs. J. Algorithms 10(2), 187–211 (1989). https://doi.org/10.1016/0196-6774(89)90012-6
Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in \(O(E\log D)\) time. Combinatorica 21(1), 5–12 (2001). https://doi.org/10.1007/s004930170002
Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52(6), 866–893 (2005). https://doi.org/10.1145/1101821.1101823
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)
Edmonds, J.: Maximum matchings and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stan. 69B, 125–130 (1965)
Franke, R., Rutter, I., Wagner, D.: Computing large matchings in planar graphs with fixed minimum degree. Theor. Comput. Sci. 412(32), 4092–4099 (2011). https://doi.org/10.1016/j.tcs.2010.06.012
Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007). https://doi.org/10.1007/s00453-007-0010-x
Hall, M., Jr.: An algorithm for distinct representatives. Am. Math. Mon. 63, 716–717 (1956)
Hopcroft, J.E., Karp, R.M.: An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225–231 (1973). https://doi.org/10.1137/0202019
Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974). https://doi.org/10.1145/321850.321852
Kobourov, S.G., Liotta, G., Montecchiani, F.: An annotated bibliography on 1-planarity. Comput. Sci. Rev. 25, 49–67 (2017). https://doi.org/10.1016/j.cosrev.2017.06.002
Lovász, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics, p. 29. North-Holland Publishing Co., Amsterdam (1986)
Micali, S., Vazirani, V.V.: An \({O(\sqrt{|V|}|E|)}\) algoithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pp. 17–27. IEEE Computer Society (1980). https://doi.org/10.1109/SFCS.1980.12
Nishizeki, T., Baybars, I.: Lower bounds on the cardinality of the maximum matchings of planar graphs. Discrete Math. 28(3), 255–267 (1979). https://doi.org/10.1016/0012-365X(79)90133-X
Petersen, J.: Die Theorie der regulären graphs (The theory of regular graphs). Acta Math. 15, 193–220 (1891)
Schaefer, M.: Crossing Numbers of Graphs. CRC Press, Boca Raton (2017)
Tutte, W.T.: A theorem on planar graphs. Trans. Am. Math. Soc. 82, 99–116 (1956). https://doi.org/10.2307/1992980
Vazirani, V.V.: A simplification of the MV matching algorithm and its proof. CoRR, abs/1210.4594 (2012). http://arxiv.org/abs/1210.4594
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Biedl, T., Klute, F. (2020). Finding Large Matchings in 1-Planar Graphs of Minimum Degree 3. In: Adler, I., Müller, H. (eds) Graph-Theoretic Concepts in Computer Science. WG 2020. Lecture Notes in Computer Science(), vol 12301. Springer, Cham. https://doi.org/10.1007/978-3-030-60440-0_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-60440-0_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-60439-4
Online ISBN: 978-3-030-60440-0
eBook Packages: Computer ScienceComputer Science (R0)