Abstract
We consider the problem of the minimum genus of a graph, a fundamental measure of non-planarity. We propose the first formulations of this problem as an integer linear program (ILP) and as a satisfiability problem (SAT). These allow us to develop the first working implementations of general algorithms for the problem, other than exhaustive search. We investigate several different ways to speed-up and strengthen the formulations; our experimental evaluation shows that our approach performs well on small to medium-sized graphs with small genus, and compares favorably to other approaches.
M. Chimani—Supported by the German Research Foundation (DFG) project CH 897/2-1.
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.
For a simple graph, the minimum genus embedding contains no face of length 1 or 2. On the other hand, we cannot be more specific than the lower bound of 3.
- 2.
In [10], the validity of such a preprocessing is shown for several non-planarity measures, namely crossing number, skewness, coarseness, and thickness. Let H be the NPC of G. We can trivially observe that (A) \(\gamma (G)\le \gamma (H)\), and (B) \(\gamma (G)\ge \gamma (H)\). A: Given an optimal solution for H, we can embed each S onto the surface in place of its replacement edge, without any crossings. B: Each replaced component S contains a path connecting its poles that is drawn crossing-free in the optimal embedding of G; we can planarly draw all of S along this path, and then simplify the embedding by replacing this locally drawn S by its replacement edge; this gives a solution for H on the same surface.
- 3.
First term: each edge lies on at most two faces, each face has size at least 3; second term: Euler’s formula with genus at least 1.
- 4.
The previous version was the winner of the Sequential Appl. SAT+UNSAT Track of the SAT competition 2014 [3]. This improved version is even faster.
References
Archdeacon, D.: The orientable genus is nonadditive. J. Graph Theor. 10(3), 385–401 (1986)
Battle, J., Harary, F., Kodama, Y., Youngs, J.W.T.: Additivity of the genus of a graph. Bull. Amer. Math. Soc. 68, 565–568 (1962)
Belov, A., Diepold, D., Heule, M.J., Järvisalo, M. (eds.): Proceedings of SAT Competition 2014: Solver and Benchmark Descriptions. No. B-2014-2 in Series of Publications B, Department Of Computer Science, University of Helsinki (2014)
Boyer, J.M., Myrvold, W.J.: On the cutting edge: simplified \(O(n)\) planarity by edge addition. J. Graph Algorithms Appl. 8(2), 241–273 (2004)
Brin, M.G., Squier, C.C.: On the genus of \(Z_3\times Z_3\times Z_3\). Eur. J. Comb. 9(5), 431–443 (1988)
Buchheim, C., Ebner, D., Jünger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: Exact crossing minimization. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 37–48. Springer, Heidelberg (2006)
Cabello, S., Chambers, E.W., Erickson, J.: Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4), 1542–1571 (2013)
Chambers, J.: Hunting for torus obstructions. M.Sc. thesis, University of Victoria (2002)
Chekuri, C., Sidiropoulos, A.: Approximation algorithms for euler genus and related problems. In: Proceedings of FOCS 2013, pp. 167–176 (2013)
Chimani, M., Gutwenger, C.: Non-planar core reduction of graphs. Disc. Math. 309(7), 1838–1855 (2009)
Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimization. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 284–296. Springer, Heidelberg (2008)
Conder, M., Grande, R.: On embeddings of circulant graphs. Electron. J. Comb. 22(2), P2.28 (2015)
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1998)
Deza, M., Fowler, P.W., Rassat, A., Rogers, K.M.: Fullerenes as tilings of surfaces. J. Chem. Inf. Comput. Sci. 40(3), 550–558 (2000)
Di Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., Vismara, L.: Drawing directed acyclic graphs: an experimental study. Int. J. Comput. Geom. Appl. 10(6), 623–648 (2000)
Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comput. Geom. 7(5–6), 303–325 (1997)
Djidjev, H., Reif, J.: An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs. In: Proceedings of STOC 1991, pp. 337–347. ACM (1991)
Edmonds, J.: A combinatorial representation for polyhedral surfaces. Not. Amer. Math. Soc. 7, 646 (1960)
Erickson, J., Fox, K., Nayyeri, A.: Global minimum cuts in surface embedded graphs. In: Proceedings of SODA 2012, pp. 1309–1318. SIAM (2012)
Filotti, I.S.: An efficient algorithm for determining whether a cubic graph is toroidal. In: Proceedings of STOC 1978, pp. 133–142. ACM (1978)
Filotti, I.S., Miller, G.L., Reif, J.: On determining the genus of a graph in \(O(V^{O(G)})\) steps. In: Proceedings of STOC 1979, pp. 27–37. ACM (1979)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the theory of NP-completeness. Bell Telephone Laboratories, New York (1979)
Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1987)
Heffter, L.: Ueber das Problem der Nachbargebiete. Math. Ann. 38, 477–508 (1891)
Juvan, M., Marinček, J., Mohar, B.: Embedding graphs in the torus in linear time. In: Balas, E., Clausen, J. (eds.) IPCO 1995. LNCS, vol. 920, pp. 360–363. Springer, Heidelberg (1995)
Kawarabayashi, K., Mohar, B., Reed, B.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: Proceedings of FOCS 2008, pp. 771–780 (2008)
Kawarabayashi, K., Sidiropoulos, A.: Beyond the euler characteristic: approximating the genus of general graphs. In: Proceedings of STOC 2015. ACM (2015)
Kotrbčík, M., Pisanski, T.: Genus of cartesian product of triangles. Electron. J. Comb. 22(4), P4.2 (2015)
Marušič, D., Pisanski, T., Wilson, S.: The genus of the GRAY graph is 7. Eur. J. Comb. 26(3–4), 377–385 (2005)
Mohar, B.: Embedding graphs in an arbitrary surface in linear time. In: Proceedings of STOC 1996, pp. 392–397. ACM (1996)
Mohar, B., Pisanski, T., Škoviera, M., White, A.: The cartesian product of 3 triangles can be embedded into a surface of genus 7. Disc. Math. 56(1), 87–89 (1985)
Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)
Myrvold, W., Kocay, W.: Errors in graph embedding algorithms. J. Comput. Syst. Sci. 77(2), 430–438 (2011)
Ringel, G.: Map Color Theorem. Springer, Heidelberg (1974)
Schmidt, P.: Algoritmické vlastnosti vnorení grafov do plôch. B.Sc. thesis, Comenius University (2012). In Slovak
Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10, 568–576 (1989)
Thomassen, C.: The graph genus problem is NP-complete for cubic graphs. J. Comb. Theor. Ser. B 69, 52–58 (1997)
Acknowledgements
We thank Armin Biere for providing the most recent version (as of 2015-06-05) of the lingeling SAT solver.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Beyer, S., Chimani, M., Hedtke, I., Kotrbčík, M. (2016). A Practical Method for the Minimum Genus of a Graph: Models and Experiments. In: Goldberg, A., Kulikov, A. (eds) Experimental Algorithms. SEA 2016. Lecture Notes in Computer Science(), vol 9685. Springer, Cham. https://doi.org/10.1007/978-3-319-38851-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-38851-9_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-38850-2
Online ISBN: 978-3-319-38851-9
eBook Packages: Computer ScienceComputer Science (R0)