Proceedings of the International Geometry Center

ISSN-print: 2072-9812
ISSN-online: 2409-8906
ISO: 26324:2012

On measures of nonplanarity of cubic graphs


Leonid Plachta


We study two measures of nonplanarity of cubic graphs G, the genus γ (G), and the edge deletion number ed(G). For cubic graphs of small orders these parameters are compared with another measure of nonplanarity, the rectilinear crossing number (G). We introduce operations of connected sum, specified for cubic graphs G, and show that under certain conditions the parameters γ(G) and ed(G) are additive (subadditive) with respect to them.

The minimal genus graphs (i.e. the cubic graphs of minimum order with given value of genus γ) and the minimal edge deletion graphs (i.e. cubic graphs of minimum order with given value of edge deletion number ed) are introduced and studied. We provide upper bounds for the order of minimal genus and minimal edge deletion graphs.

Ключові слова:
Для цієї мови відсутні ключові слова


Як цитувати
Plachta, L. (2018). On measures of nonplanarity of cubic graphs. Proceedings of the International Geometry Center, 11(2).


1. Joseph Battle, Frank Harary, Yukihiro Kodama, J. W. T. Youngs. Additivity of the genus of a graph. Bull. Amer. Math. Soc., 68:565–568, 1962.

2. Daniel Bienstock, Nathaniel Dean. Bounds for rectilinear crossing numbers. J. Graph Theory, 17(3):333–348, 1993.

3. Gruia Călinescu, Cristina G Fernandes, Ulrich Finkler, Howard Karloff. A better approximation algorithm for finding planar subgraphs. J. Algorithms, 27(2):269–302, May 1998.

4. Luerbio Faria, Celina M. Herrera de Figueiredo, Sylvain Gravier, Candido F. X. de Mendonça, Jorge Stolfi. On maximum planar induced subgraphs. Discrete Appl.Math., 154(13):1774–1782, 2006.

5. Luerbio Faria, Celina M. Herrera de Figueiredo, Candido F. X. Mendonça. On the complexity of the approximation of nonplanarity parameters for cubic graphs. Discrete Appl. Math., 141(1-3):119–134, 2004.

6. Jean-Luc Fouquet, Henri Thuillier. On some conjectures on cubic 3-connected graphs. Discrete Math., 80(1):41–57, 1990.

7. M. R. Garey, D. S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312–316, 1983.

8. Jonathan L. Gross. Embeddings of cubic Halin graphs: genus distributions. Ars Math. Contemp., 6(1):37–56, 2013.

9. Jonathan L. Gross, Thomas W. Tucker. Topological graph theory. Dover Publications, Inc., Mineola, NY, 2012.

10. R. K. Guy. A combinatorial problem. Nabla (Bulletin of the Malayan Mathematical Society), 7:68–72, 1960.

11. J. F. P. Hudson. Piecewise linear topology. University of Chicago Lecture Notes prepared with the assistance of J. L. Shaneson and J. Lees. W. A. Benjamin, Inc., New York-Amsterdam, 1969.

12. Ed Pegg Jr, G. Exoo. Crossing number graphs. The Mathematica Journal, 11(2):161–170, 2009.

13. Gary L. Miller. An additivity theorem for the genus of a graph. J. Combin. Theory Ser. B, 43(1):25–47, 1987.

14. Bojan Mohar, Carsten Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.

15. Bojan Mohar, Andrej Vodopivec. The genus of Petersen powers. J. Graph Theory, 67(1):1–8, 2011.

16. Roman Nedela, Martin Škoviera. Atoms of cyclic connectivity in cubic graphs. Math. Slovaca, 45(5):481–499, 1995.

17. Shengjun Pan, R. Bruce Richter. The crossing number of 11 is 100. J. Graph Theory, 56(2):128–134, 2007.

18. L. Plachta. On minimal genus cubic graphs. in preparation.

19. Gerhard Ringel. Map color theorem. Springer-Verlag, New York-Heidelberg, 1974. Die Grundlehren der mathematischen Wissenschaften, Band 209.32 L. Plachta

20. László A. Székely. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1-3):331–352, 2004. 6th International Conference on Graph Theory.

21. Carsten Thomassen. The graph genus problem is NP-complete. J. Algorithms, 10(4):568–576, 1989.

22. Nicholas C. Wormald. Classifying -connected cubic graphs. In Combinatorial mathematics, VI (Proc. Sixth Austral. Conf., Univ. New England, Armidale, 1978), volume 748 of Lecture Notes in Math., 199–206. Springer, Berlin, 1979.