This is a coding project by Josh Mermelstein and Michael James in the summer of 2012 for the
Tufts CS departament. Its goal is to create a program that can take a
non-planar graph and determine if there is a way to make it planar by copying
any number of vertices while preserving connections.
The overall structure is centered on a circular doublely linked list which is
specified in the circ_list files.
the following is the format in which the program reads in a graph:
the first line will be the number of vertices
every subsequent line will represtent a new vertex whose index is the line
number -1
Each of these lines will end in a newline character.
The program internally runs from 0->n-1 but all inputs and outputs should be from 1->n.
some known information.
Planar Expandable graphs
K_6
K_{3,4}
K_{2,2,3}
K_{3,3,1}
K_{4,2,1}
K_7 with 4 edges missing (all 4 sharing a vertex)
(make a drawing of a K_6 and put a new vertex inside of a triangle)
K_7 with 4 edges missing (no vertex missing more than 2)
(example of missing edge set, 12, 34, 35, 56
make a K_2211 and put the final vertex in the square)
Proven non-planar expandable
K_7
K_{4,4}
K_{3,5}
Suspected expandable
suspected non expandable
any two planar expandible graphs connected by one edge
a K_7 with two edges missing (not sharing a vertex)
a K_7 with two edges missing (sharing a vertex)
Running theories
Eli:
40% undecidable, 55% linear time solvable, 5% more than linear time
Ben:
Maybe decidable but worth considering that it is undecidable.
If it is decidable, then no vertex needs to be used more than twice
Michael:
It could be anywhere from undecidable to NP-complete.
Josh:
Probably decidable
If one can partition the verticies into two sets such that each set is
non-planar (even if that set is planar expandable) then the graph is not
planarexpanable. (also the graph is connected)