17
\$\begingroup\$

A simple graph is toroidal if it can be drawn on the surface of a torus without any edges intersecting. Your task is to take a simple undirected graph via any reasonable method (adjacency matrix, edge vertex sets, etc.) and decide whether or not it is a toroidal graph. You should output one of two distinct values for each of the two decisions. You may choose what these values are.

This is so answers will be scored in bytes with less bytes being better.

Test Cases

Here Kn is the complete graph with n vertices and Kn,m is the complete bipartite graph.

Toroidal

Not Toroidal

  • K8
\$\endgroup\$
  • 12
    \$\begingroup\$ Actual test cases would be helpful, for instance a few adjacency matrices. People are probably able to convert it to another appropriate format if they have to. \$\endgroup\$ – Stewie Griffin Aug 25 '17 at 18:44
  • 2
    \$\begingroup\$ web.math.ucsb.edu/~padraic/ucsb_2013_14/math137b_s2014/… the theorem at the end states: "If G is toroidal, then the Euler characteristic of G is 0" \$\endgroup\$ – Giuseppe Aug 25 '17 at 19:03
  • 6
    \$\begingroup\$ What are K₃, K₇, K₃,₃ and K₈? \$\endgroup\$ – Erik the Outgolfer Aug 25 '17 at 19:16
  • 2
    \$\begingroup\$ Looks like the general purpose algorithm for this is quite extensive and probably beyond the scope of PPCG. See the Yu (2011) paper mentioned at: mathoverflow.net/questions/119493/toroidality-testing. If "maybe" is a suitable answer I've got a short 1-liner :) \$\endgroup\$ – Kelly Lowder Aug 25 '17 at 19:48
  • 6
    \$\begingroup\$ @KellyLowder This is not meant to be an easy question. I don't really think there is a scope of difficulty on PPCG, after all we have the implement tetris in GoL question. \$\endgroup\$ – Sriotchilism O'Zaic Aug 25 '17 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.