×

Counting hexagonal patches and independent sets in circle graphs. (English) Zbl 1239.05093

Summary: A hexagonal patch is a plane graph in which inner faces have length 6, inner vertices have degree 3, and boundary vertices have degree 2 or 3. We consider the following counting problem: given a sequence of twos and threes, how many hexagonal patches exist with this degree sequence along the outer face? This problem is motivated by the enumeration of benzenoid hydrocarbons and fullerenes in computational chemistry. We give the first polynomial time algorithm for this problem. We show that it can be reduced to counting maximum independent sets in circle graphs, and give a simple and fast algorithm for this problem. It is also shown how to subsequently generate hexagonal patches.

MSC:

05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blank, S.J.: Extending immersions of the circle. Ph.D. thesis, Brandeis University, Waltham, MA, USA (1967)
[2] Bonsma, P., Breuer, F.: Finding fullerene patches in polynomial time I: counting hexagonal patches. arXiv: 0808.3881v1 (2008) · Zbl 1272.05189
[3] Bonsma, P., Breuer, F.: Finding fullerene patches in polynomial time. In: Proceedings of the 20th International Symposium on Algorithm and Computation (ISAAC 2009). Lecture Notes in Computer Science, vol. 5878, pp. 750–759. Springer, Berlin (2009) · Zbl 1272.05189
[4] Bornhöft, J., Brinkmann, G., Greinus, J.: Pentagon–hexagon-patches with short boundaries. Eur. J. Comb. 24(5), 517–529 (2003) · Zbl 1022.05018 · doi:10.1016/S0195-6698(03)00034-9
[5] Bouchet, A.: Reducing prime graphs and recognizing circle graphs. Combinatorica 7(3), 243–254 (1987) · Zbl 0666.05037 · doi:10.1007/BF02579301
[6] Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999) · Zbl 0919.05001
[7] Brinkmann, G., Coppens, B.: An efficient algorithm for the generation of planar polycyclic hydrocarbons with a given boundary. MATCH Commun. Math. Comput. Chem. 62(1), 209–220 (2009) · Zbl 1273.92079
[8] Brinkmann, G., Dress, A.W.M.: A constructive enumeration of fullerenes. J. Algorithms 23(2), 345–358 (1997) · doi:10.1006/jagm.1996.0806
[9] Brinkmann, G., Nathusius, U. v., Palser, A.H.R.: A constructive enumeration of nanotube caps. Discrete Appl. Math. 116(1–2), 55–71 (2002) · Zbl 0993.05137 · doi:10.1016/S0166-218X(00)00328-0
[10] Brinkmann, G., Delgado-Friedrichs, O., von Nathusius, U.: Numbers of faces and boundary encodings of patches. In: Graphs and Discovery, Proceedings of the DIMACS Workshop on Computer Generated Conjectures from Graph Theoretic and Chemical Databases. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 69, pp. 27–38. AMS, Providence (2005) · Zbl 1095.05036
[11] Brinkmann, G., Graver, J.E., Justus, C.: Numbers of faces in disordered patches. J. Math. Chem. 45(2), 263–278 (2009) · Zbl 1260.92125 · doi:10.1007/s10910-008-9403-6
[12] Deza, M., Fowler, P.W., Grishukhin, V.: Allowed boundary sequences for fused polycyclic patches and related algorithmic problems. J. Chem. Inf. Comput. Sci. 41, 300–308 (2001) · doi:10.1021/ci000060o
[13] Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005) · Zbl 1074.05001
[14] Dutour Sikirić, M., Deza, M., Shtogrin, M.: Filling of a given boundary by p-gons and related problems. Discrete Appl. Math. 156(9), 1518–1535 (2008) · Zbl 1144.05026 · doi:10.1016/j.dam.2006.11.020
[15] Endo, M., Kroto, H.W.: Formation of carbon nanofibers. J. Phys. Chem. 96, 6941–6944 (1992) · doi:10.1021/j100196a017
[16] Eppstein, D., Mumford, E.: Self-overlapping curves revisited. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 160–169. SIAM, Philadelphia (2009)
[17] Francis, G.K.: Extensions to the disk of properly nested plane immersions of the circle. Mich. Math. J. 17(4), 377–383 (1970) · Zbl 0203.25804 · doi:10.1307/mmj/1029000526
[18] Gabor, C.P., Supowit, K.J., Hsu, W.L.: Recognizing circle graphs in polynomial time. J. ACM 36(3), 435–473 (1989) · Zbl 0825.68417 · doi:10.1145/65950.65951
[19] Gavril, F.: Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3(3), 261–273 (1973) · Zbl 0259.05125 · doi:10.1002/net.3230030305
[20] Graver, J.E.: The (m,k)-patch boundary code problem. MATCH Commun. Math. Comput. Chem. 48, 189–196 (2003) · Zbl 1052.52014
[21] Guo, X., Hansen, P., Zheng, M.: Boundary uniqueness of fusenes. Discrete Appl. Math. 118(3), 209–222 (2002) · Zbl 0996.92040 · doi:10.1016/S0166-218X(01)00180-9
[22] Mohar, B., Thomassen, C.: Graphs on Surfaces. John Hopkins University Press, Baltimore (2001) · Zbl 0979.05002
[23] Nash, N., Lelait, S., Gregg, D.: Efficiently implementing maximum independent set algorithms on circle graphs. ACM J. Exp. Algorithmics 13, 1.9 (2008) · Zbl 1284.05305
[24] Seidel, R.: The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom. 19(1), 1–17 (1998) · Zbl 0892.68100 · doi:10.1007/PL00009330
[25] Shor, P.W., Van Wyk, C.J.: Detecting and decomposing self-overlapping curves. Comput. Geom. 2(1), 31–50 (1992) · Zbl 0760.68086 · doi:10.1016/0925-7721(92)90019-O
[26] Spinrad, J.P.: Recognition of circle graphs. J. Algorithms 16(2), 264–282 (1994) · Zbl 0797.68130 · doi:10.1006/jagm.1994.1012
[27] Supowit, K.J.: Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 6(1), 93–94 (1987) · Zbl 05449801 · doi:10.1109/TCAD.1987.1270250
[28] Valiente, G.: A new simple algorithm for the maximum-weight independent set problem on circle graphs. In: Proceedings of the 14th International Symposium on Algorithm and Computation (ISAAC 2003). Lecture Notes in Computer Science, vol. 2906, pp. 129–137. Springer, Berlin (2003) · Zbl 1205.05171
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.